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

문제

가장 큰 수 (https://programmers.co.kr/learn/courses/30/lessons/42746)

풀이

1. 초기 접근

• 조합을 이용하여 완전 탐색.

  • 가장 먼저 떠오르는 직관적인 방법은, numbers 에 있는 모든 변수들을 조합하여 만든 수들 중, 가장 큰 값을 반환하는 것이다.
  • 이럴 경우, 조합하는 시간은 약 O(len(numbers)!) 이다.
  • 그런데, 조건에 보면, 1 < numbers < 100,000 이란다. O(100000!) 은 절대 1초 내로 안들어오므로, 이 알고리즘은 사용할 수 없다.

number 를 정렬한다거나, 탐색할 때, O(n log n) 안으로 해결 해야 한다는걸 늘 생각해야 한다.
보통, 이렇게 루프로 시간문제가 걸리는 경우, 배열 내 아이템을 '미리' 전처리 해주는 방법을 쓰곤한다.

생각해보자. 어떻게 하면 numbers 를 한 번만 루프를 돌게하면서도, 서로 다 비교할 수 있게 할 수 있을까?
numbers 의 모든 수에 어떤 적절한 변형을 주어, 우리가 원하는 비교를 할 수 있게 할 수 있을까?

• numbers 내 모든 수를 4자리수로 만든다.

  • numbers의 원소는 0 이상 1,000 이하라는 조건을 주목해보자. 1000이라는 숫자가 괜히나온게 아닌거 같다.
  • 문제에 주어진 두 제한 조건을 살펴보면, 1000 * 100000 = 10^8 이다. 이는 1억이라는 숫자인데, 이 안에 루프를 돌아도 딱 1초를 넘지 않는다. 느낌이 딱온다. 1000이라는 숫자가 그냥 나온게 아니다.
  • 이제 이렇게 생각해볼 수 있다.
  • numbers 의 모든 수에 접근하되, 모든 숫자가 4자리수가 되게 만들어, 이렇게 만들어진 수들끼리 비교(정렬) 한뒤, 큰 수부터 차례대로 이어붙이면 가장 큰 수가 되지않을까?!
  • 4자리 수가 되게하는 방법은, 어떤 수가 4자리 수가 될 때까지 계속해서 10을 곱하는 것이다.
  • 예를 들어 4 -> 4000이 되게하고, 35 -> 3500이 되게한다.
  • 3과 30의 경우, 똑같이 3000이 되는데, 3이 30보다 더 앞에 놓아져야 330 으로, 30이 앞에 놓이는 303 보다 크므로, 3, 30에서 우리는 3에 더 우선순위를 줘야한다.

• 코드

def solution(numbers):
    l = []
    for number in numbers:
        original = number
        while number < 1000:
            number *= 10
        l.append([number, original])
    l = sorted(l, key=lambda x : (-x[0], x[1]))
    return str(int("".join([str(number[1]) for number in l])))

2. 생각못한 변수

위 같이 풀면, 실행 시 테스트 케이스는 통과하는데, 통과용 테스트 케이스는 통과못한다.
이유가 뭘까????

질문 게시판을 헤집던 중, 예외 케이스 하나를 발견했는데, 아래 입력을 주면 오답이 나왔다.

input : [121, 12]

correct output : 12121
my output : 12112

오답이 나오는 이유는 간단했다. 위 알고리즘을 그대로 적용하면

121 -> 1210 이 되고, 12 -> 1200 이 된다.
1210 > 1200 이므로, 숫자가 놓이는 순서는 [121, 12] 가 되고, 반환하는 값은 12112가 되는 것이다.
근데 정답은 [12, 121] 로 놓여 만들어진 숫자 12121 이다. (12121 > 12112 이므로)

이거… 알고리즘 완전 잘못잡은거 같은데.. 이제 어떻게 해야할까?
따로 예외케이스를 잡아주는 코드를 넣어야 할까?

3. 4자리 만들기를 좀 더 현명하게.

오랜 고민 끝에, 다시 질문게시판을 헤집던 중 다음과 같은 힌트를 발견했다.

4자리 수를 만들 때, 10을 곱해나가며 4자리수를 만들어나가는게 아니라, 그 수를 반복시켜 만드는 것이다.
예를 들어, 12 -> 1200 이 아니라 12 -> 1212가 된다. 또 3 -> 3000 이 아니라, 3 -> 3333이 된다.
이러면, 기존의 모든 비교 기준도 만족시킬 뿐 아니라, [121, 12] 도 해결한다!!

코드를 다음과 같이 바꾸었다.

• 코드

def solution(numbers):
    l = []
    for number in numbers:
        original = str(number)
        number = list(str(number))
        i = 0
        while len(number) <= 4:
            number.append(original[i])
            i = (i + 1) % len(original)
        number = int("".join(number))
        l.append([number, original])

    # ex1. [6, 10, 2]
    # l = [[66666, '6'], [10101, '10'], [22222, '2']]
    # ex2. [3, 30, 34, 5, 9] 
    # l = [[33333, '3'], [30303, '30'], [34343, '34'], [55555, '5'], [99999, '9']]

    l = sorted(l, reverse=True)
    return str(int("".join([item[1] for item in l])))

안되던 테스트케이스도 모두 통과했다.

오늘의 교훈은, 끝까지 더 집요하고, 현명하게 생각해보자는 것이다.

더 나은 풀이

같은 아이디어인데, 훨씬 더 깔끔하게 코드를 짠 풀이가 있어 가져와본다.

def solution(numbers):
    numbers = list(map(str, numbers))
    numbers.sort(key=lambda x: x*3, reverse=True)
    return str(int(''.join(numbers)))

출처 : 윤종석 , 김세환 , 한진욱 , 김나래 , 전민구 외 14 명 (프로그래머스)

위 풀이와 기본 아이디어는 같다.
다만 훨씬 더 깔끔한 이유는, 아래와 같다.

• map 을 활용한 점
• (list) * 3 를 활용해, 훨씬 더 파이썬스럽게 짰다는 점

아직도 참 갈 길이 멀구나 싶다.