[프로그래머스] 가장 큰 수 Python

문제

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한 사항

numbers의 길이는 1 이상 100,000 이하입니다.
numbers의 원소는 0 이상 1,000 이하입니다.
정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

입출력 예

numbers	return
[6, 10, 2]	"6210"
[3, 30, 34, 5, 9]	"9534330"

(Wrong) 접근법 1

• 문제와 테스트 케이스를 처음 접하고 든 생각은, "문자열 리스트로 맵핑해서 앞글자부터 비교해서 큰 수로 정렬하면 되겠다!" 였다. (조건1)
• 그런데 2번째 테스트 케이스에서 3이 30보다 앞에 와야 한다는 조건 (330 > 303) 을 맞추게 하기 위해서 "마지막 숫자랑 첫 번째 숫자를 비교해서 더 큰 것이 앞에 오면 된다"고 생각했다.
• 왜냐하면, 3, 30, 32, 34가 있다고 한다면, 34, 32, 3, 30 순서로 정렬해야 할 텐데, 이는 마지막 숫자랑 첫 번째 숫자를 비교해서 큰 것은 더 앞으로 가고, 아닌 것은 뒤로 가면 된다고 생각했기 때문이다.

def solution(numbers):

  ## 조건 1 (문자열은 자동적으로 길이가 길면 더 큰 것으로 파악된다.)
  numbers = list(map(str, numbers))
  numbers = sorted(numbers, reverse=True)

  ## 조건 2 
  numbers = sorted(numbers, key=lambda x : x[-1], reverse=True)

  answer = ''.join(numbers)
  return answer

<반례>

• 하지만, numbers의 원소는 2자리까지 있는 것이 아니라, 1000 이하이기 때문에 최대 4자리까지 올 수 있다는 사실을 잊었다.
• 따라서 위의 풀이 방식은, 2자리 이상의 숫자문자열이 있을 때에도 마지막 글자들만 비교해서 문제를 일으킨다. 아래의 반례들을 찾을 수 있다.
  
  
  

(Wrong) 접근법 2

• 문자열의 길이가 4까지 있을 수 있다는, 제한적인 상황임이 확인되었으니, 앞 자리부터 순차적으로 비교해가면 된다고 생각했다.
• for 문을 조건 형식으로 내가 구현을 하려고 하면, O(N^2) 알고리즘을 짜게 될 것 같아서, sorted의 key 함수를 작성하여 최악의 경우에도 O(NlongN) 을 보장하고자 하였다.
• 알고리즘은 앞 자리부터 순차적으로 크기를 비교해가되, 만약 문자열의 길이가 i(0<=i<=3)보다 작거나 같다면, 마지막 자릿수를 비교하도록 하였다.
• 그리고 answer를 반환하는 부분에 str(int(answer))로 작성하였는데, 이는 0이 여러개 있는 경우에는 이를 '000'으로 반환하는 것이 아니라 '0'으로 반환해야 하기 때문이었다.

def solution(numbers):
    i = 0
    numbers = list(map(str, numbers))

    def function(x):
        if i < len(x):
            return x[i]
        else:
            return x[-1]

    for _ in range(4):
        numbers = sorted(numbers, key=function, reverse=True)
        print(numbers)
        i += 1

    answer = ''.join(numbers)
    return str(int(answer))

<반례>

• 테스트 케이스 4를 보면, '101'과 '110'의 위치가 3번째줄부터 잘못되는 것을 볼 수 있다. 앞 두 자리를 비교할 때는 '110'이 '101'보다 크게 반영되고 있지만, 3번째 이후부터는 '101'이 '110'보다 크다고 계산되기 때문이다.
• 여기서 깨달은 점은, 각 자리의 수를 각각 비교해야 하는 것이 아니라, 복합적으로 앞자리를 우선 순위에 두고 알고리즘을 짜야겠다는 것이었다. 😂

(Wrong) 접근법 3

• 앞자리부터 우선순위를 가지고 답을 찾으면 된다고 생각했으니! sorted 함수의 key 함수를 튜플로 반환하게끔 하여 풀면 되겠다고 생각했다.
• 올바른 비교를 위하여, 앞글자부터 순차적으로 접근하되, 마지막 글자를 반복하여 4개의 글자로 맞춰주었다.
• 이렇게 만들 경우 튜플의 앞부분부터 우선순위로 비교하여, 마지막 글자까지 순차적으로 비교할 수 있다. 예를 들어 '3'과 '30'를 비교할 때 '3333'과 '3000'로 만들어서 비교하게끔 하였다.

def solution(numbers):
  numbers = list(map(str, numbers))

  def function(x):
    if len(x) == 4:
      return (x[0], x[1], x[2], x[3])
    elif len(x) == 3:
      return (x[0], x[1], x[2], x[2])
    elif len(x) == 2:
      return (x[0], x[1], x[1], x[1])
    elif len(x) == 1:
      return (x[0], x[0], x[0], x[0])

  numbers = sorted(numbers, key=function, reverse=True)
  # print(numbers)
  
  answer = ''.join(numbers)
  return str(int(answer))

<반례>

• 솔직히,,, 이번엔,,, 모든 테스트 케이스에서 맞을 줄 알았는데 띠로리 공식 테케에서도 1~6번이 풀리지 않았고, 테케를 더 찾아서 넣어보니 반례가 발생했다.
• '123'과 '1233'을 비교한다고 해보자! function에서 비교할 값으로 반환하는 값은 둘 다 '1233', '1233'이 되어서 결국 똑같게 되고, 순서가 변동하지 않게 된다. 이처럼 끝에 반복되는 글자가 있을 시에는 제대로 순서가 반영되지 않는다는 문제가 생긴다.
• 테스트 4번은 위에서도 봤던 것인데, '110'과 '101'은 올바르게 잡혔지만, '10', '100', '1000'이 난리가 났다.
• 여기에는 반영하지 않았지만, '978', '9788'과 같은 케이스, 즉 마지막 글자가 반복되는 경우에는 제대로 숫자가 반영될 수 없다는 문제가 있다.
  
  
  

(Right!) 접근법 4

• 반복되는 글자들이 있는 게 문제라면... 어떻게 하면 좋을까 하다가 헤매는 시간을 가졌다.
• 처음에 든 생각은 마지막 글자 (x[-1])가 첫 번째 글자(x[0]) 보다 크거나 작은 것이 문제가 되는가? 를 생각했다. 그런데 x[-1]이 x[0]보다 작으면 x[0]을 채워야 하고, x[-1]이 x[0]보다 커도 x[0]을 채워야 한다...? 는 걸 발견!...

123 < 1233 
978 > 9788
10 > 100 > 1000

• 위와 같은 케이스들을 보면서 어떻게 규칙이 나올 수 있을지 고민했다.
• 우리는 현재 정확한 비교를 위해 4자리를 모두 채워 튜플을 만들고 있다. 이를 올바르게 하기 위해서는 "마지막 글자만 계속 반복하게 하는 것이 아니라, 마지막 글자가 끝난 다음에는 다시 맨 처음 글자부터 순차적으로 채워야한다"는 것을 발견했다😂
• 예를 들어서, '123'은 '1233'으로 채우는 것이 아니라, '1231'로 채워야 한다.
• '978'도 '9788'이 아닌 '9789'로 채우면 위의 케이스가 성립한다.
• '10'은 '1010'으로 채우고, '100'은 '1001'로 채운다. 그러면 위의 케이스가 성립한다.

def solution(numbers):
    numbers = list(map(str, numbers))

    def function(x):
        if len(x) == 4:
            return (x[0], x[1], x[2], x[3])
        elif len(x) == 3:
            return (x[0], x[1], x[2], x[0])
        elif len(x) == 2:
            return (x[0], x[1], x[0], x[1])
        elif len(x) == 1:
            return (x[0], x[0], x[0], x[0])

    numbers = sorted(numbers, key=function, reverse=True)
    # print(numbers)

    answer = ''.join(numbers)
    return str(int(answer))

느낀점

• 당장 주어진 테스트 케이스를 맞추는 것만 생각하면, 많은 반례에 맞닥뜨리게 되는 것 같다.
• 실전 시험에서는 히든 케이스를 내가 생각해내야 할텐데,,, 실력이 많이 부족하다고 느꼈다.
• 그래도 여러 번 시도하면서 문제를 풀어내는 과정은 재미있었다. 다만 이제 좀 더 처음부터 올바르게 조건을 생각하며 접근하고, 시간도 단축할 수 있도록 노력해야겠다. 😀