백준(BaekJoon) 1422번 : 숫자의 신 - python 풀이

JISU LIM·2023년 1월 10일

Algorithm Study Records

목록 보기

23/79

❓1422번 : 숫자의 신

〽️ 문제 요약

가지고 있는 K개의 수 각각을 최소 한 번씩 사용하여 N개의 수를 뽑을 때 이 수들을 붙여서 만들 수 있는 가장 큰 수를 구하면 되는 문제

🤨 접근법

여러 방법을 생각했다. 큰 순서대로 정렬해서 붙이는 방법, 문자열 길이, 큰 순서로 정렬해서 붙이는 방법 등등.. 하지만 생각했던 어떤 방법도 모든 예제 및 반례를 통과하지 못했다.

여러 레퍼런스를 참고한 결과, 핵심은 수를 붙여서 만들 수 있는 가장 큰 수를 만드는 것이다. 그렇다면 실제로 붙여봤을 때 더 큰 방향으로 정렬을 수행하면 된다.

레퍼런스 중 하나에서 설명한 예시로, 9989와 998을 정렬한다고 할 때 9989 + 998 / 998 + 9989 두 경우 중에는 전자가 더 크지만, 7787과 778을 정렬할 때 7787+778 / 778+7787 에서는 후자가 더 크다. 즉 실제 붙였을 때 큰 수를 고르면 되는 것.

그리고 문제의 조건 중 가지고 있는 K개의 수 보다 사용해야 하는 N개의 수가 더 크면, K개의 수 중 일부를 중복해서 사용해야 하는데, 이는 명백하게 K개의 수 중 가장 큰 수를 N-K 번만큼 더 사용하면 가장 큰 수를 만들 수 있다.

🔡 코드

방법 1 : 두 수를 붙였을 때 큰 순서대로 정렬하기 (직접 구현)

import sys

K, N = map(int, input().rstrip().split())

def _sort(arr):
	for i in range(len(arr)):
		for j in range(i+1, len(arr)):
			a = int(arr[i]+arr[j])
			b = int(arr[j]+arr[i])
			if a < b:
				arr[i], arr[j] = arr[j], arr[i]

arr = [input().rstrip() for _ in range(K)]
max_value = max(arr)
for _ in range(k, n):
	arr.append(max_value)

_sort(arr)

print(*arr, sep='')

맨 앞 원소 i부터 뒤의 원소 j와 하나씩 붙여봤을 때 i+j가 크다면 현 순서를 유지하고, j+i가 크다면 순서를 바꾼다. 즉, 전체 이 과정을 수행하게 되면 붙였을 때 큰 순으로 정렬이 수행된다.

방법 2 : 두 수를 붙였을 때 큰 순서대로 정렬하기 (sort와 cmp_to_key 활용)
```
import sys
from functools import cmp_to_key

input = sys.stdin.readline

def cmp(x : int, y : int):
    if int(str(x)+str(y)) > int(str(y)+str(x)):
        return -1
    else:
        return 1

K, N = map(int, input().rstrip().split())
num_list = [int(input().rstrip()) for _ in range(K)]
max_value = max(num_list)
for _ in range(K, N):
    num_list.append(max_value)
num_list.sort(key = cmp_to_key(cmp))

print(*num_list, sep='')
```
Python3 부터 sort함수의 key 인자에 cmp_to_key(func) 형태로 원하는 조건을 형식에 맞게 구현하면 이에 따라 sorting을 할 수 있는 기능을 제공한다. key 인자에 주어야 하는 cmp_to_key 메서드는 functools 모듈에서 가져올 수 있다. cmp_to_key의 매개변수로 들어가는 func에 본인이 원하는 조건을 구현하는 것인데, 인자 두 개(x, y)를 주어서 두 인자를 활용해 조건식을 구현하고, 조건에 따라 두 수를 바꿔야 하면 양수를 반환, 현 순서를 유지해야 하면 음수를 반환하도록 구현해야 한다. 문제를 예로 살펴보면 두 수(x, y)를 붙여봤을 때 x+y가 더 크다면 현 순서를 유지(음수 반환)해야 하고, y+x가 크다면 두 순서를 바꿔야 한다(양수 반환). 따라서 다음과 같이 함수를 정의할 수 있다.
```
def cmp(x : int, y : int):
	if int(str(x)+str(y)) > int(str(y)+str(x)):
		return -1
	else:
		return 1
```

📚 고찰

sort와 lambda식을 활용할 줄 알아서 이제 대부분의 정렬을 무난하게 수행할 수 있을 줄 알았는데 아니었다. 조금 더 입맛에 맞게 조건에 따라 정렬하기 위해서는 방법 1과 같이 직접 정렬 함수를 구현하고나 cmp_to_key와 함께 적절한 조건 비교 함수를 정의해서 구현해야 한다.

잘 응용하면 아주 유용하게 사용 가능할 수 있는 함수같다. 워낙 임팩트가 강해서 기억에 남을 것 같다.

처음 경험하는 플래티넘 문제.. 맵다..