문제 링크
풀이 과정
- 가장 직관적인 방법은, numbers의 각 원소의 조합으로 생성된 숫자 중 가장 큰 수를 고르는 것입니다
- 하지만, numbers의 최대 길이가 10^5이므로, 무조건 시간 초과가 발생하게 됩니다.
- 분명히, 가장 큰 수를 구하는 과정은 모든 경우의 수를 고려하는 작업을 포함합니다.
- 쉽사리, 해결 방법이 떠오르지 않을 수 있습니다.
- 이때, 우리가 참고하지 않은 힌트가 한 개 있습니다. 무엇일까요? 바로, numbers의 원소가 가질 수 있는 값의 범위입니다.
- numbers에 속한 각 원소는 최대 1,000의 값을(정수) 가질 수 있습니다.
- 이 말을 다르게 해석하면, 원소의 최대 문자열 길이는 4입니다.
- 이 사실을 근거로, 우리는 원소 간 우선 순위를 정할 수 있습니다! 아래와 같이 말이지요!
- ex) 문자열 ‘9’와 ‘34’ 우선 순위 비교
- ‘9 ‘→ ‘999’ (문자열 x3) / ‘34’ → ‘343434’ (문자열 x3)
- 최대 문자열 길이가 4이므로, 문자 ‘9’를 문자열 ‘999’로 뻥튀기 시키는 것입니다!!
- ‘999’ > ‘343434’
- 문자열의 우선 순위는 왼쪽부터 오른쪽 순서대로 비교합니다. 따라서, 이 경우에는 ‘999’가 우선 순위가 더 높겠네요!
- 제한 사항이 결정적인 문제 풀이 힌트가 될 수 있다는 사실을 명심합시다!
전체 코드
def solution(numbers):
numbers = list(map(str, numbers))
numbers.sort(key=lambda x: x*3, reverse=True)
return str(int(''.join(numbers)))
유사 문제