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

728x90

문제설명

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]	"6120"
[3, 30, 34, 5, 9]	"9534330"

문제해설

가장 큰 수 문제는 그냥 읽어보면 되게 쉬워보인다.

그냥 앞자리 수로 정렬해주면 되지 않을까?

생각보다 그렇게 쉽게 해결할 수 있는 문제가 아닐 것이다.

예를 들어서 아래와 같은 케이스가 존재한다고 보자

[9, 98, 997, 988, 989, 998]

이 때의 가장 큰 수는 무엇일까?

앞 자리수만 본다면, 그냥 순서대로 붙여버려도 될 것인데, 실상 문제를 해결하기엔 그렇지 않다.

위 문제의 정답은 아래와 같다.

999899798998988

[9, 998, 997, 989, 98, 988]

어떻게 위와 같은 결과가 나왔을까?

일단, 이 문제의 관건은 앞 자리수에 가장 큰 수들만을 선별하여 배치하는 것이다.

가장 큰 예시로 9와 98을 붙이면 998이 된다.

또한 998과 998을 붙이면 998998이 될 것이다.

하지만, 9와 998을 붙이면 9998이라는 더 큰 앞자리를 만들 수 있다.

즉, 앞자리가 큰 9가 붙는 위치에 따라서 숫자의 대소관계가 달라진다는 것이다.

그렇다면 어떻게 이 문제를 해결할 수 있을까

이 문제의 정답은 자릿수이다.

생각해보자, 앞 선 예시에 8이라는 값이 추가되었다고 가정하면,

9와 8 그리고 98, 998, 988의 5개의 숫자의 순서는 어떻게 설정해야 할까

이 때, 입력은 0부터 1000이 들어올 수 있다.

그렇다면 우리는 0부터 1000이 되는 숫자들이 모든 자리에 배치될 경우를 고려해주면 된다.

본인은 이 문제를 해결하기 위해 6번을 반복해서 숫자를 배치했다.

그리고, 앞에서 6자리를 슬라이싱 했다.

최종적으로 그렇게 반복된 숫자를 기준으로 정렬을 수행했다.

아래와 같이 말이다.

기존 숫자	반복된 숫자	정렬 후 인덱스
9	999,999	0
98	989,898	3
997	997,997	2
988	988,988	4
989	989,989	2
998	998,998	1

위 표를 보면 알 수 있듯, 자리수에 따른 값의 크기를 알 수 있다.

모든 자릿수에서의 경우를 고려한 배열의 정렬을 수행할 수 있게 된 것이다.

위 반복된 숫자에서 집중해서 볼 것은 첫번째 자릿수도 중요하지만, 그 뒤로 이어서 내려오는 숫자의 자릿수이다.

배열을 간단하게 줄여보자

[9, 8, 98, 998]

위 네 개의 numbers가 입력으로 들어오면 우리는 9, 998, 98, 8 순으로 배열을 정렬해야 된다.

앞 자리수로만 수행하면 운이 좋다면 위와 같은 결과를 얻을 수도 있겠지만,

아마, 98과 998의 배치로 인해 문제를 해결할 수 없게 될 것이다.

그래서 우리는 모든 경우를 살피기 위해 6번의 반복을 수행한 것이다.

989898과 998998을 보았을 때, 정렬에 큰 역할을 수행하는 두번째 자릿수를 고려할 수 있게 되기 때문이다.

코드를 확인하기 전, 입력 숫자로 0이 들어올 수 있음을 고려해야 된다.

11번 케이스가 그 경우인데, 입력이 모두 0으로 들어오는 경우, 우리는 '0'을 리턴해야 한다.

(숫자로 아무리 조합해도 0보다 크게 나올 수 없기 때문이다.)

거두절미하고 문제를 해결한 코드를 확인해보자

정답코드

def solution(numbers): 
    tmp = sorted([(i, int((str(num)*8)[:6])) for i, num in enumerate(numbers)], key=lambda x: -x[1])
    answer = ''
    for i, _ in tmp: answer += str(numbers[i])
    return answer if answer[0] != '0' else '0'
    
solution([9, 98, 997, 988, 989, 998]) # 999899798998988

위와같이 간단한 로직으로 문제를 해결할 수 있다.

코드를 다시 곱씹어보며 문제를 이해할 수 있으면 좋겠다.