백준(Python) 풀이/정렬

백준(Python) 1422번 숫자의 신 풀이

개발윗미 2022. 9. 28. 09:40

Python으로 구현한 1422번 숫자의 신 문제 풀이입니다.

 

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

 

1422번: 숫자의 신

첫째 줄에 K와 N이 공백을 사이에 두고 주어진다. K와 N은 각각 50보다 작거나 같은 자연수이고, N은 K보다 크거나 같다. 둘째 줄에는 K개의 수가 한 줄에 하나씩 주어진다. 각 수는 1,000,000,000보다

www.acmicpc.net


from functools import cmp_to_key

k, n = map(int, input().split())
data = [int(input()) for _ in range(k)]
max_value = max(data)

for _ in range(k, n) : # n - k 만큼 가장 큰 수를 추가
    data.append(max_value)

data.sort(key=cmp_to_key(lambda x, y: int(str(y)+str(x)) - int(str(x)+str(y))))
print(*data, sep='')

 

1. cmp_to_key()와 lambda 를 통해 주어진 값들의 정렬을 수행하여 문제를 해결할 수 있다.

 

2. k개의 수를 입력받아 data 리스트에 할당하고, 그 중 가장 큰 값을 max_value에 할당한다.

 

3. n-k 개만큼 max_value 값을 data 리스트에 추가한다.

 

4. 각 수를 문자로 변환하여 두 문자를 이어붙였을 때 더 큰 값을 구성하여 정렬을 수행한 뒤 data 리스트의 모든 수를 이어 붙여 출력한다.

 


** 추가

- cmp_to_key()에서 cmp란 compare 함수를 의미한다.

# compare 구조
def compare(x, y) :
    if x+y > y+x :
        return -1
    elif x+y == y+x :
        return 0
    else :
        return 1
        
# 활용
from functools import cmp_to_key

def compare(x, y) :
    if x+y > y+x :
        return -1
    elif x+y == y+x :
        return 0
    else :
        return 1

data = ['34', '37', '9', '31', '3']
print(sorted(data, key=cmp_to_key(compare)))

# [결과] ['9', '37', '34', '3', '31']
# 즉, '9'와 '37'의 경우 '937' > '379' 이므로 9가 먼저 온다.
(1) return 음수 : 먼저 들어온 요소가 앞으로 정렬된다.

(2) return 0 : 바뀌지 않는다.

(3) return 양수 : 나중에 들어온 요소가 앞으로 정렬된다. (먼저 들어온 요소보다 앞에 배치)

 

- 이와 같이 cmp_to_key를 활용해 조건에 따라 정렬을 수행할 수 있다.

 

 


[참고]

https://blog.pjookim.me/entry/Python-BOJ-1422-%EC%88%AB%EC%9E%90%EC%9D%98-%EC%8B%A0

https://velog.io/@heyday_7/python-%EC%A1%B0%EA%B1%B4-%EC%A0%95%EB%A0%AC-%ED%95%98%EA%B8%B0-cmptokey