[Python - Greedy, Sort] 1422 숫자의 신 (Platinum-4)

📌 문제

숫자의 신은 여러명이 있지만, 그 중에 자연수의 신은 오세준이다. 오세준은 자연수의 신으로 오래오래 살다가 어느 날 음수의 신과 전쟁을 하게 되었다. 오세준은 음수의 신 이다솜을 이기기위해서 큰 숫자를 만들기로 했다.

오세준은 지금 K개의 자연수를 가지고 있다. 오세준은 K개의 수 중에 정확하게 N개의 수를 뽑아내서 그 수를 붙여서 만들 수 있는 수중에 가장 큰 수를 만들고자 한다. 같은 수를 여러 번 이용해도 된다. 단, 모든 수는 적어도 한 번은 이용되어야 한다.

오세준이 현재 가지고 있는 K개의 수가 주어졌을 때, 이 수를 적어도 한 번 이상 이용해서 만들 수 있는 수 중에 가장 큰 수를 출력하는 프로그램을 작성하시오.

예를 들어 지금 오세준이 2, 3, 7 이라는 3개의 수를 가지고 있고, 4개의 수를 뽑아야 한다면, 7732를 만들면 가장 큰 수가 된다.

📌 입력

첫째 줄에 K와 N이 공백을 사이에 두고 주어진다. K와 N은 각각 50보다 작거나 같은 자연수이고, N은 K보다 크거나 같다. 둘째 줄에는 K개의 수가 한 줄에 하나씩 주어진다. 각 수는 1,000,000,000보다 작거나 같은 자연수이다. 이 수는 중복되어 들어올 수 있다. 만약 중복되어서 들어오는 경우에는 각 수가 적어도 입력으로 주어진 만큼 이용되어야 한다는 소리다.

📌 출력

N개의 수를 뽑아서 연결해서 만들 수 있는 가장 큰 수를 출력한다.

📌 문제 풀이

👨‍🏫 접근

너무 어려웠다. 분명 맞게 풀었고 게시물에 있는 모든 반례들이랑 내가 생각했던 반례들을 모두 테스트했는데 실패했다.

 

그 코드가 왜 틀렸는지는 나중에 테스트 해보기로 하고 다른 풀이로 문제를 풀었다. 바로 정렬을 사용했다.

 

리스트를 정렬하는 방법은 다음과 같다. 두 숫자를 앞 뒤로 붙여봐서 더 큰 수를 찾아내는 것이다.

 

9989와 998을 정렬한다고 해볼 때, 9989/998과 998/9989 중에서는 전자가 더 크다. 그런데 비슷하게 7787과 778을 정렬할 때는 7787/778과 778/7787에서 후자가 더 크다. 즉 정렬할 때는 더 큰 숫자나 그런 것이 아니라 둘이 더해서 더 큰 경우를 기준으로 해야 한다는 점이다. 

👨‍🏫 문제 풀이

📄 전체 코드

import sys
input = sys.stdin.readline
k, n = map(int, input().split())


def do_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 = str(max(map(int, arr)))

for _ in range(k, n):
    arr.append(MAX)

do_sort(arr)

print(''.join(arr))

📄 준비

import sys
input = sys.stdin.readline
k, n = map(int, input().split())

...

arr = [input().rstrip() for _ in range(k)]

MAX = str(max(map(int, arr)))

for _ in range(k, n):
    arr.append(MAX)

가장 큰 값을 여러 번 반복해야 가장 큰 수가 되므로 가장 큰 수를 배열에 넣어준다.

📄 풀이

def do_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]

...

do_sort(arr)

print(''.join(arr))

 

좌측에 가장 큰 값을 넣어야 하므로 인덱스를 계속 이동하면서 해당 인덱스 이상의 인덱스를 모두 검사해서 옮긴다.

📌 총평

너무 어려웠다... 후....