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

링크: https://school.programmers.co.kr/learn/courses/30/lessons/42746

프로그래머스

 

처음 생각한 풀이:

32 3222 34 3444 라는 예제를 보고, 맨 뒤만 반복하여 4자리로 정렬 기준 수를 만들어준 뒤 (3222 3222 3444 3444) 이 숫자로 정렬하고, 만약 정렬 기준 수가 같을 때는 원래 수가 더 짧은 기준 정렬 수를 a, 긴 기준 정렬 수를 b라고 했을 때 a[0] > a[-1]이면 a를 앞에 두고, 아니면 b를 앞에 두었다. 이럴 경우 위와 같은 예제를 해결할 수 있고, 뒷부분이 반복되는 경우를 잡을 수 있다고 생각했다.

 

틀린 이유:

12 1213이라는 반례가 있었다. 3번째 자리까지 같고 4번째 자리에 더 큰 수가 오는 경우를 생각하지 못했다. 

 

풀이:

수를 세 번 반복한 뒤 비교해야 했다. 처음 생각한 풀이에서 맨 앞과 맨 뒤만 비교한 데서 오류가 있었다. a[0]과 a[-1]을 비교한 후에 a[-1]과 a[-2]도 비교해야 하는 것이 틀린 이유였는데, 이것은 결국 문자를 반복하는 것과 같은 효과를 낸다. 따라서 수를 문자열로 바꿔 세 번 반복하고 각 자릿수를 비교하면 된다. 

 

풀이 코드:

 

numbers = list(map(int, sys.stdin.readline().split()))
tps = []
res = ''

for num in numbers:
    num_str = str(num)
    tps.append((num_str, num_str*3))

tps = sorted(tps, key=lambda x:x[1], reverse=True)
for tp in tps:
    res += str(int(tp[0]))