[Python] BOJ(백준) 16496번 - 큰 수 만들기

1. 링크

https://www.acmicpc.net/problem/16496

2. 난이도

플래티넘5

3. 풀이

	from functools import cmp_to_key
	n = int(input())
	arr = list(map(int, input().split()))
	def compare(x, y):
	if str(x)+str(y) > str(y)+str(x):
	return -1
	if str(x)+str(y) < str(y)+str(x):
	return 1
	return 0
	arr.sort(key=cmp_to_key(compare))
	count = 0
	for elem in arr:
	if elem == 0:
	count += 1
	if count == len(arr):
	print(0)
	else:
	for elem in arr:
	print(elem, end='')

view raw BOJ16496.py hosted with ❤ by GitHub

functools 모듈의 cmp_to_key를 사용했다. 이 cmp_to_key는, 람다로는 불가능한 두 연산값들끼리의 비교를 할 때 유용하게 사용할 수 있다.

우선 문제 자체에 대해서는 그냥 수들을 이어붙여서 최댓값을 만들기만 하면 되는 문제였는데, 어떻게 최댓값을 만드는지를 생각하기가 어려운 문제였다고 생각한다. 결론부터 이야기하면 직접 두 숫자 a, b를 ab, ba 형태로 붙여봤을 때 값이 더 큰 경우에 해당하는 숫자가 앞으로 오도록 정렬 기준을 설정하면 된다. 그리고 이 ab와 ba의 크기를 비교하는 것을 cmp_to_key로 할 수 있다.

arr내의 두 값을 이어 붙인 값이 클수록 앞으로 위치하게 되고 작을수록 뒤로 위치하게 되어 arr.sort(key=cmp_to_key(compare))로 이러한 배열이 완성이 된다.

다만 여기에서 주의해야 할 점은 0이 여러개 있을 경우 그 0을 전부 출력하는 것이 아닌, '0' 하나만 출력해야 되므로 정렬한 배열 arr에서 0의 개수가 arr의 길이와 같은 경우에 한해 0만 출력하도록 예외설정을 해주면 된다.