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

문제 풀이 정리

 

문제 설명

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"

코드

def solution(numbers):
    answer = ''
    
    numbers = sorted(numbers)
    
    from functools import cmp_to_key
    def compare_function(a,b):
        str_a = str(a)
        str_b = str(b)
        
        if(a == b):
            return 1
        
        for x, y in zip(str_a, str_b):
            if int(x) < int(y):
                return 1
            elif int(x) > int(y):
                return -1
        
        shorter = "0"
        longer = "0"
        if len(str_a) < len(str_b):
            longer = str_b
            shorter = str_a
        elif len(str_a) == len(str_b):
            return -1
        else:
            longer = str_a
            shorter = str_b
        
        if int(shorter+longer) > int(longer+shorter):
            return 1
        else:
            return -1
    
    new_numbers = sorted(numbers, key = cmp_to_key(compare_function))
    answer = "".join([str(number) for number in new_numbers])
    answer = str(int(answer))

    return answer

 

풀이과정의 단편적 생각들...

 

아 레벨2 라 그런지 오지게 오래 걸렸다. 한문제 푸는데...

문제도 짧고 별로 안어려워서 시작했는데 풀수가 없더라

 

1. 첫번째 난관

[3, 30, 34] 의 경우 앞자리가 3으로 동일하기 때문에 3, 30, 34 로 정렬됐었다.

이 경우에는 같은 자리 까지 비교한뒤 (앞자리 3) 나머지 자리와 (0, 4) 와 3 과 비교해 큰지 작은지를 대조했었다.

결과는 [34(1,2자리 모두 3이상), 3, 30(1의 자리숫자가 0으로 3보다 작기때문)] => "34330" 으로 잘나왔었다.

 

하지만 채점시 시간초과 및 결과가 틀리다고 나와 하루정도 머리를 쥐어 뜯었고....

결국 힌트를 보게 된다.

 

2. 두번째 난관

[0, 0, 0] 의 경우 내 첫번째 코드의 경우 "000" 이였다. 이건 큰 "수" 가 아니다. 수는 0으로 나와야 된다.

 

채점시 한문제가 정답처리된걸 확인했지만 또 어디선가 문제가 났는지 나머지 다른 케이스에서 오답이 나온다....

 

3. 세번째 난관

[10, 101] => "10110" 이 되어야 하고, [898, 89] => "89 898"이 되어야 한다. 차이점이 보이시나? (did you see that??)

10 , 101 의 비교시에는 위 [3,30,34] 처럼 앞자리만 비교해도 되지만

89 , 898 의 경우, 결과로 "89889"(>"89898") 이 되어야 하기 때문에 작은쪽 앞자리와 긴쪽의 숫자들을 비교하는 로직이 통하지 않는다...

 

나의 나쁜 버릇 중 하나가 그냥 눈과 머리로만 결과를 생각하기 때문에 놓치는 것이 많다는 생각이 이때 들었다

무의식 적으로 종이에 숫자들을 쓰다가 찾아냈다.

 

그냥 (길이가 작은쪽+길이가 큰쪽) / (길이가 큰쪽+길이가 작은쪽) 을 단순히 문자열 결합후 비교 하면 되지 않을까?!?!?

 

이렇게 다사다난한 딱 한문제 풀이가 완료되었다..

 

소요 시간 : 체감 1주일....