[백준] 16496번 큰 수 만들기 ★

💡문제접근

• 처음 시도한 방법은 조합이었다. 만능이라고 생각했던 combinations를 이용해서 가장 큰 수를 만드는 코드를 작성했는데 이 방법은 시간초과(TLE)가 발생했다.
• 두 번째로 시도한 방법은 그리디였다. 입력받은 수 중에서 숫자의 길이가 가장 긴 수에 맞춰 나머지 수들을 늘려주는 방식으로 코드를 작성했다. 하지만 이 방법은 코너 케이스가 존재하여 WA를 받았다.
• 세 번째로 시도한 방법 역시 그리디였다. 입력받은 수를 전부 다 10자리보다 작은 숫자로 길이를 늘려주어 변형한 수와 기존 수를 리스트에 넣어 내림차순 정렬한 뒤 join을 이용해서 출력하는 방법을 이용했다.

💡코드(메모리 : 31256KB, 시간 : 48ms)

import sys
input = sys.stdin.readline

N = int(input())
li = list(map(int, input().strip().split()))

result = []
for i in li:
    s = str(i)
    length = len(s)
    while len(s) < 10:
        s += s[len(s) - length]
    result.append([int(s), int(i)])
result.sort(key = lambda x : x[0], reverse=True)

ans = []
for i in result:
    ans.append(i[1])
print(int(''.join(map(str, ans))))

📌 조합을 이용한 코드

from itertools import permutations
import sys
input = sys.stdin.readline

N = int(input())
li = list(map(int, input().strip().split()))

Max = -1
for i in permutations(li, len(li)):
    i = int(''.join(map(str, i)))
    if i > Max:
        Max = i
print(Max)

📌 그리디를 이용한 코드(코너 케이스 존재)

import sys
input = sys.stdin.readline

N = int(input())
li = list(map(int, input().strip().split()))

Maximum_length = 0
for i in li:
    i = str(i)
    if Maximum_length < len(i):
        Maximum_length = len(i)

result = []
for i in range(len(li)):
    length = len(str(li[i]))
    if length == Maximum_length:
        result.append([int(li[i]), li[i]])
    else:
        temp = str(li[i]) * (Maximum_length - length + 1)
        result.append([int(temp), li[i]])
result.sort(key = lambda x : x[0], reverse=True)

ans = ""
for i in range(len(result)):
    ans += str(result[i][-1])
print(ans)

💡코너 케이스

Input

3
10 100 1004

Output

101001004

Answer

101004100

💡소요시간 : 34m