[프로그래머스] 가장 큰 수. 반례와 경우의 수 나열

시도

• BruteForce로 비교 못함
  • 배열의 길이가 N 일 때 O(N!) 만큼 시간이 걸려 문자열을 생성해서 비교해야 한다. 생성된 문자열을 숫자로 바꾸어 비교해야하는데, 이때 숫자의 최대 길이는 1e5 * 1e3 으로 1e8 (숫자의 크기가 아니라 숫자의 길이라는데 유의) 이기 때문에 이 숫자를 2진수로 표현만 해도 약 41.52MB 를 잡아 먹는다. ( 10^(10^8) 에 밑이 2인 log를 취한 값 만큼 비트가 필요함 )
• 가장 먼저 떠올리기 쉬운 정렬인 ‘사전식 순서(lexicographical order)’ 정렬을 해도 안 풀림
  • [2,20,9] 을 사전식으로 정렬하면 [2,20,9] 가 나온다.
    • 사전에서는 더 짧은 숫자가 앞에 나오기 때문이다.
    • 큰 수를 만들기 위해서는 이걸 거꾸로(reverse) 해야 하는데, [9,20,2] 은 [9,2,20] 보다 작다.
    • 그렇다고 마지막에 더 길게 남는 문자를 앞으로 빼기에는 [9,24,2] 의 경우가 반례다.

정답 코드

from functools import cmp_to_key

def compare(a, b):
    if a + b > b + a:
        return -1
    else:
        return 1

def solution(numbers):
    numbers = list(map(str, numbers))
    sorted_numbers = sorted(numbers, key=cmp_to_key(compare))
    answer = ''.join(sorted_numbers)
    return answer if answer[0] != '0' else '0'

해설

• sort 조건을 정해주고 sort
  • python3는 비교할 수 있는 key값을 지정해주는 방식이다
  • python2나 javascript는 비교함수를 이용해 요소들을 비교한다.
  • functools 의 cmp_to_key를 이용하면 python2 스타일로 비교할 수 있다.
  • cmp(self, other) 가 들어왔을 때 더 앞에 가야 하는 값이 음수를 반환하게 하면 된다. (보통 -1) 반환
• 비교 방법
  • 배열 안의 두 숫자 a,b 를 두 문자가 합쳐졌을 때 더 큰 숫자가 되는 순서로 정렬하면, 최종 정렬 결과는 가장 큰수가 된다.
  • 식으로 나타내면 a+b 와 b+a 중 더 큰 숫자가 되는 것을 고르면 된다.

  def compare(a, b):
      if a + b > b + a:
          return -1
      else:
          return 1
  

• 엣지 케이스
  • 0 이 여러개 있는 배열이 있을 수 있다.
  • 다른 숫자가 섞여있다면 상관없지만, 0만 있다면 000 은 숫자가 아니기 때문에 ‘0’으로 나오도록 처리해줘야 한다.

  return answer if answer[0] != '0' else '0'
  

다른 풀이

• 위 풀이가 가장 명확하다고 생각하지만 프로그래머스에서 가장 높은 순위에 있는 풀이가 있다.

def solution(numbers):
    numbers = list(map(str, numbers))
    numbers.sort(key = lambda x: x * 3, reverse=True)
    return str(int(''.join(numbers))) # 00 을 0 으로 처리하기 위해 str->int->str 과정을 거침

• 위의 간단한 방법(a+b 와 b+a를 비교)을 외면하고 모든 경우의 수를 따져볼 경우 다음과 같다.
• 길이가 1인 숫자 비교 - 큰 숫자가 먼저
• 앞글자가 같고 길이가 2, 3인 숫자간 비교 - 큰 숫자가 먼저
• 앞글자가 같고 길이가 다른 경우
  • 길이 1, 길이 2
    • 두번째 자리가 첫번째 자리보다 큰 경우 ex) 3, 34 - 길이 2 우선
    • 두번째 자리가 첫번째 자리와 같은 숫자 ex) 3, 33 - 상관 없음
    • 두번째 자리가 첫번째 자리보다 작은 경우 ex) 3, 30 - 길이 1 우선
  • 길이 1, 길이 3 - 2번째 자리비교로 결정. 두번째자리까지 같을 시 경우 나눔
    • 세번째 자리가 첫번째 자리보다 큰 경우: ex) 3, 334 - 길이 3 우선
    • 세번째 자리가 첫번째 자리와 같은 경우: ex) 3, 333 - 상관 없음
    • 세번째 자리가 첫번째 자리보다 작은 경우: ex) 3, 331- 길이 1 우선
  • 길이 2, 길이 3
    • 세번째 자리가 첫번째 자리보다 큰 경우 ex) 32, 324 - 길이 3 우선
    • 세번째 자리가 첫번째 자리와 같은 경우 ex) 32, 323 - 길이 3 우선
    • 세번째 자리가 첫번째 자리보다 작은 경우 ex) 32, 321 - 길이 1 우선
  • 길이 2, 길이 4 - 대부분 첫째자리, 세번째 자리 비교하면 되고, 세번째까지 같을 시 경우를 나눔
    • 네번째 자리가 두번째 자리 보다 큰 경우: ex) 32, 3234 - 길이 4 우선
    • 네번째 자리가 두번째 자리와 같은 경우: ex) 32, 3232 - 상관 없음
    • 네번째 자리가 두번째 자리 보다 작은 경우: ex) 32, 3231 - 길이 2 우선
• 위와 같이 따진 걸 보면 길이가 더 긴 숫자와 비교하기 위해 짧은 숫자는 다시 앞자리부터 비교를 이어 나간다는 걸 확인할 수 있다.
• 그걸 가장 간단하게 구현하는 방법이 문자를 반복시켜서 순차적으로 비교하는 방법이다.
• 반복은 더 짧은 문자의 길이가 긴문자의 길이와 같거나 길어질 정도만 반복하면 되고 긴 문자는 최대 길이가 3이므로, 그냥 양쪽에 *3을 하면 된다. (1000의 경우 엣지케이스인데, 1과 비교했을 때 후순위이므로 따로 처리해줄 필요 없다.)

나의 단순한 풀이와 반성

def makeSort(num):
    base = int(num[0])
    result = base
    for i in range(1,len(num)):
        c = num[i]
        curr = int(c)
        result += (curr - base) / 100 ** i
        prev = curr
    
    return result

def solution1(numbers):
    *numbers, = map(str,numbers)
    numbers.sort(reverse = True, key = lambda x: makeSort(x))
    answer = ''.join(numbers)
    return answer if answer[0] != '0' else '0'

• 첫째, 둘째까지 같고 길이가 다른 숫자를 비교할 때, 더 앞에와야 하는 수는 직전 수보다 뒤에 오는 숫자가 얼마나 큰지에 의해 결정된다고 생각했고, 그 때문에 가중치를 줘서 차이를 소수점으로 더해줬다.
• 자리마다 소수점 하나씩만큼만 가중치를 줄여나가면 다른 숫자인데 같은 value를 같는 경우 (49, 50) 가 있어서 0.01씩 가중치를 줬다.
• 하지만 전제부터 틀렸기 때문에 계속 정답이 되지 않았다.
• 반례 - [13, 132] : 마지막수(2)가 직전수 (3) 보다 작음에도 불구하고 앞에 와야 더 큰수가 만들어지는 경우가 있다.
• 그렇다면 마지막수를 첫번째 수와 비교해야 하냐 하면 그것도 아니다.
  • [202, 20] : 마지막수(2)가 첫번째 수 (2) 와 같음에도 불구하고 길이 3인 숫자가 앞에 와야 유리하다.
  • [121, 12] : 마지막수(1)이 첫번째 수 (1)와 같음에도 불구하고 길이 2인 숫자가 앞에 와야 유리하다.
  • 즉, 길이에 관한 가중치도 간단한 것이 아니다.

반성

• 모든 경우의 수를 따져보지 않고, ‘대충 이렇게 돌려보면 되겠지’ 하고 테스트 케이스 맞으면 제출하고 틀리면 그제서야 반례를 찾아보는 경우가 많다.
• 그렇게 자세한 케이스를 안 따지다보니, 케이스를 넣었을 때 실제 값이 어떻게 나오는지 비교하는 능력도 떨어지고 케이스를 찾는 능력도 떨어지는 것 같다.
• 후행적으로라도 이렇게 하나하나 케이스를 나열해 보는 습관을 들여야겠다.
• 더 좋은 건 문제 풀 때, 엣지와 코너 케이스들을 최대한 나열해 보는 것!

추가

• 처음에 푼 방법의 반례가 도저히 생각이 나지 않아서, 정답 코드가 만들어내는 테스트 케이스와 비교를 해보았다. 추후에도 도움이 될 것 같아 포스팅해본다.