문제
중복 없는 수는 각 숫자(1, 2, 3, ..., 9)가 최대 한 번씩 등장하고, 숫자 0은 포함하지 않는 수이다. 따라서 중복 없는 수는 최대 9자리로 이루어질 수 있다. 중복 없는 수의 예시로는 9, 32, 489, 98761, 983245 등이 있다.
정수 N이 주어질 때, N보다 크면서 가장 작은 중복 없는 수를 출력하는 프로그램을 작성하라.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 각 줄에 정수 N(0 ≤ N ≤ 999,999,999)이 주어진다.
출력
각 테스트 케이스마다 답을 출력한다. 만약 답에 해당하는 수가 없는 경우는 0을 출력한다.
풀이 및 회고
풀이
우선 중복 없는 수에 대한 리스트를 재귀를 통해 미리 생성한다. 이후 while문에서 입력을 받을 때마다 이분 탐색을 통해 적절한 수를 찾아 출력하면 된다. 예외적으로 입력이 987,654,321보다 크거나 같다면 이보다 더 큰 중복 없는 수는 만들 수 없으므로 0을 출력하도록 한다.
회고
오랜만에 골드 문제를 봐서 그런가 보자마자 숨이 턱 막혔다. 그래서 알고리즘 분류에 손이 가버렸는데 보자마자 코드가 떠올랐다. 쫄지말고 한번 해볼걸..ㅠ 그러나 떠오른 것과 짤 수 있는건 달랐다. 순열 코드가 기억이 안나는 바람에 조금 걸렸다..ㅎㅎ 내일도 골드를 풀까..?
코드
def make_nls(mxlen: int, cnt: int, used: bin, val: int):
if cnt >= mxlen:
number_list.append(val)
else:
for i in range(9):
if used & (1 << i):
continue
make_nls(mxlen, cnt + 1, used | (1 << i), val * 10 + numbers[i])
numbers = [i for i in range(1, 10)]
number_list = [0]
for i in range(1, 10):
make_nls(i, 0, 0, 0)
while True:
try:
n = int(input())
if n >= 987654321:
print(0)
else:
start = 0
end = len(number_list)
while start + 1 < end:
mid = (start + end) // 2
if number_list[mid] <= n:
start = mid
else:
end = mid
if number_list[start] <= n:
print(number_list[end])
except EOFError:
break
