백준 16496번 큰 수 만들기 파이썬

리뷰

나의 첫번째 플래티넘 문제 도전기였다.

자료구조, 그리디 알고리즘, 정렬에는 자신이 있었기에 문제를 읽었을 때 플래티넘 문제가 이렇게 쉽다고? 라는 생각이 들었다.

문제풀이

처음 생각했을 땐 리스트를 문자열로 받아와 문자열 수로 오름차순 1차 정렬 후 int로 변환 하여 내림차순으로 2차 정렬 하는 방식으로 접근했으나 질문 게시판에 있던 반례에 걸리게 되었다.

 

그래서 수로 주어질 범위가 10억보다 작거나 같은 음이 아닌 정수이므로 문자열의 길이가 10 이상이 되도록 곱해주어 오름차순으로 정렬 후 마지막에 reverse=True 처리해 주었다. 그렇게 되면 한자릿수의 숫자가 입력 되더라도 0이 아닌 경우 항상 10억 이상의 수가 되기 때문에 예외 케이스 없이 정렬이 되었다.

 

이후 리스트내 요소를 join 해주어 문자열을 생성하고 문자열의 처음이 0일 경우 0을 리턴(0밖에 없는 케이스) 아닐 경우 문자열을 그대로 리턴해 주었다.

추천반례

2
378 3788
ans : 3788378

6
1 2 3 10 11 12
ans : 321211110

3
101 1012 1014
ans : 10141012101

4
15 159 150 15001
ans : 1591515015001

 

정답코드

def q16496():
    # 백준 16496번 파이썬 큰 수 만들기
    n = int(input())
    lst = input().split()
    lst.sort(key=lambda x: x * 10, reverse=True)
    result = ''.join(lst)
    if lst[0] == '0':
        print('0')
        return
    print(result)
q16496()