가장 큰 수 - 프로그래머스[Level 2], 코드 비교하기

문제

[1,2,3,4,5,6] 같은 int 형 list 가 들어왔을때, 모두 이어 붙혔을 때 가장 큰 수를 찾는 단순한 문제

 

시도

처음에는 단순하게 조합을 구하고 거기서 가장 큰 수를 찾으면 되겠다, 라고 생각했으나 가만 생각해보면 모든 조합을 구할때  원소가 100,000개라면 시간 복잡도가 난리날 것으로 예상했다.

참고

1 2 3

from itertools import permutations    permutations(numbers, i) #i 는 몇개를 가지고 조합을 할 지 결정

cs

 

역시나 시도해본 결과, 전부 시간 초과가 발생했다 :)

그래서 두번째 시도를 했다. 생각한 알고리즘을 설명하자면, 각 원소마다 앞에 있는 값을 비교해 가면서 같으면 다음 원소를 비교하고, 다를 때 정렬을 시켜주는 식으로 내가 직접 sorting 의 key를 작성했다.

코드는 비교적 빠르게 작성할 수 있었고, output 값을 join 하는 부분이 막혀서 디버깅을 통해서 맞춰주기만 했다.

코드

def sorting(left, right):
    left = list(map(int, list(str(left))))
    right = list(map(int, list(str(right))))
    i, j = 0, 0
 
    while i != len(left) and j != len(right):
        if left[i] > right[j]:
            return left, right
        elif left[i] < right[j]:
            return right, left
        i += 1
        j += 1
    # 여기는 두 수 중에 끝의 인덱스에 다다를때까지 같은 경우이다.
    if len(left) == len(right):
        return left, right
    elif len(left) > len(right):
        for x in range(i, len(left)):
            if left[x] > right[-1]:
                return left, right
            elif left[x] < right[-1]:
                return right, left
        return left, right
    elif len(left) < len(right):
        for x in range(j, len(right)):
            if left[-1] > right[x]:
                return left, right
            elif left[-1] < right[x]:
                return right, left
        return left, right
 
 
def solution(numbers):
    answer = ''
    for a in range(len(numbers) - 1):
        for b in range(a + 1, len(numbers)):
            x, y = sorting(numbers[a], numbers[b])
            numbers[a], numbers[b] =  int(''.join(map(str, x))), int(''.join(map(str, y)))
    print(numbers)
    return answer
 
solution([3,30,34,5,9])

짜면서도 생각은 했지만, 1/3 정도는 맞고 나머지는 시간 초과가 발생했다. 뭔가 더 효율적인 코드가 있을까 해서 찾아보았다.

 

정답 코드

코드를 보니 역시나 웃음만 나왓다.ㅋㅋ; 

코드를 설명하자면 str 로 모든 원소를 바꾼 상태에서 lambda 함수를 통해서 key 값에 *3 을 적용한다. 적용한 이유는 원소의 최대 크기가 1000이기 때문에 자리수 비교를 위해서 *3 만큼 해준 것이다. python 에서 str 의 sorting 과정은 맨 앞 인덱스의 ASCII 값을 통해서 진행되기 때문에 원래 내가 생각했던(?) 흐름과 동일하게 흐를 것이다. 큰 수를 찾는 것이기 때문에 reverse 해주고 join 해주면 된다.

(사실 원래 나도 key값만 잘 조작하면 될 것 같다고 보자마자 알았지만, x*3 을 생각하지 못했다. 그래서 직접 구현해 본것 .. 블로그에 정리해 놓고 다음에 사용할 수 있도록 참고하겠다.)

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