[백준] 18511번 큰 수 구성하기

www.acmicpc.net/problem/18511

18511번: 큰 수 구성하기

 

문제

N보다 작거나 같은 자연수 중에서, 집합 K의 원소로만 구성된 가장 큰 수를 출력하는 프로그램을 작성하시오. K의 모든 원소는 1부터 9까지의 자연수로만 구성된다.

예를 들어 N=657이고, K={1, 5, 7}일 때 답은 577이다.

 

입력

첫째 줄에 N, K의 원소의 개수가 공백을 기준으로 구분되어 자연수로 주어진다. (10 ≤ N ≤ 100,000,000, 1 ≤ K의 원소의 개수 ≤ 3) 둘째 줄에 K의 원소들이 공백을 기준으로 구분되어 주어진다. 각 원소는 1부터 9까지의 자연수다.

단, 항상 K의 원소로만 구성된 N보다 작거나 같은 자연수를 만들 수 있는 경우만 입력으로 주어진다.

 

출력

첫째 줄에 N보다 작거나 같은 자연수 중에서, K의 원소로만 구성된 가장 큰 수를 출력한다.

 

 

풀이

입력받은 target보다 작거나 같은 수 중에서 K원소로만 구성된 가장 큰 수를 만들기 위해서
입력받은 수를 저장한 배열을 역으로 정렬했다.

import sys
max_value , N = map(int,input().split())
len_max = len(str(max_value))

numbers = list(map(int, sys.stdin.readline().split()))
numbers.sort(reverse= True)
answer = 0
for i in range(len_max) :
    for j in range(len(numbers)):
        temp = numbers[j]*(10**(len_max-1-i))
        if answer + temp  <= max_value :
            answer += temp
            break


print(answer)

 

그 후 2중 반복문을 이용하여 각 자리수를 계산했는데 예제에서는 문제 없이 통과했었다.
하지만 이렇게 계산하는 경우 입력에서 100의 자리 숫자는 맞출 수 있지만 10의자리 숫자에서 맞추지 못하는 경우
만들 수 없는 숫자가 나오게 된다.

 

위의 경우 77이 결과로 나와야하지만 607이라는 숫자가 나오게 되는 것이다.
10의 자리 숫자를 만족하지 못한 것이 0으로 채워지는 문제가 발생했다.

 

그래서 itertools에 있는 product함수를 이용하여 만들 수 있는 모든 수를 만들어서 하나씩 비교해서 계산하는 것으로 변경하였다.

import sys
import itertools

max_value , N = map(int,input().split())
len_max = len(str(max_value))

numbers = list(map(int, sys.stdin.readline().split()))
numbers.sort(reverse= True)

prod = list(itertools.product(numbers,repeat=N))

for i in prod:
    temp = ''.join(map(str,i))
    if max_value >= int(temp):
        print(temp)
        break

이 경우에도 예제는 통과했지만 numbers에 있는 가장 작은 숫자가 target의 제일 큰자리 숫자보다 작은 경우
해당하는 값이 없어서 결과가 나오지 않았다.

22가 최소값이기 때문에 결과가 나오지 않는 것이다. 반복을 N번해서 답이 없는 경우에는 N-1번해서 답을 찾아야한다.

 

전체 코드

import sys
import itertools

max_value , N = map(int,input().split())
len_max = len(str(max_value))

numbers = list(map(int, sys.stdin.readline().split()))
numbers.sort(reverse= True)
len_numbers = len(numbers)
flag = 0

while not flag :
    prod = list(itertools.product(numbers,repeat=len_max))
    for i in prod:
        temp = ''.join(map(str,i))
        if max_value >= int(temp):
            print(temp)
            flag = 1
            break

    len_max -= 1

길이가 N부터 비교해서 답이 없는 경우에는 N-1로 비교를해서 찾는 방식으로 변경하였다.

while안에 for문이 존재해서 탈출을 위해서 flag와 break를 모두 사용한 것이 깔끔하지는 않지만 모든 테스트케이스에
대해서 통과할 수 있었다.