[Python] 11037번 중복 없는 수

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

11037번: 중복 없는 수

---

 

24/02/20

 

 

원래는 파이썬으로 통과해서는 안되는 문제인데, 파이썬이 점점 빨라짐에 따라 쉽게 통과할 수 있게 된 문제 같다.

 

정확한 시간 복잡도는 계산해보지 못했다.

---

 

문제 접근 방식:

 

 

문제에서 요구하고자 하는 것은 주어지는 수보다 크면서 가장 작은 중복 없는 수를 구하는 것이다.

 

중복 없는 수란, 각 숫자가 최대 한 번씩만 등장하고, 숫자 $0$을 포함하지 않는 수를 일컫는다.

 

처음에 생각한 방법은 아주 나이브한 방법이었다. 그리고 그 방법이 시간 내에 돌아갔다.

 

수를 입력 받으면, 그 수를 $1$씩 올려가며 수가 중복 없는 수가 되는지 확인한다.

 

그러다 중복 없는 수 조건을 만족시키면 종료시키고, 그 수를 반환한다.

 

먼저, 불가능한 경우를 생각하기 위해 가장 큰 중복 없는 수인 $987,654,321$을 생각했다.

 

이 수보다 크거나 같다면 무조건 불가능하다. 따라서 $-1$을 반환하도록 했다.

 

또한, 빠른 동작을 위해 $9876$과 같은, $9$로 시작하여 $1$씩 내림차순으로 배열된 수를 입력받으면 바로 $12345$와 같은 중복 없는 수를 내뱉도록 예외처리를 진행해 주었다.

 

만약 이 코드가 없었더라면 $98765432$를 입력받으면 $123456789$를 출력하기까지 $24691357$번을 동작했을 것이다.

 

이 예외처리는 '123456789'문자열과 '987654321'문자열 두 개를 활용하여 구현하였다.

 

두 개의 예외 처리를 진행한 뒤, 중복 없는 수를 확인하는 check함수를 만들어 중복 없는 수인지 아닌지를 확인했다.

 

수를 문자열로 변환하여, 이를 확인하는 방식을 취했다.

 

시간 내로 왜 돌아가는지는 구체적으로 분석하지는 못했다. 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더 보기를 누르면 확인할 수 있다.

# 11037번 중복 없는 수
# 그리디
import sys
input = sys.stdin.readline

def check(N):
    c = [0]*10
    N = str(N)
    for i in range(len(N)):
        if c[int(N[i])] or N[i] == '0':
            return False
        c[int(N[i])] = 1
    return True

def solve(N):
    if N >= 987654321:
        return 0
    K = len(str(N))
    if N >= int('987654321'[:K]):
        return int('123456789'[:K+1])
    while True:
        N += 1
        if check(N):
            break
    return N

while True:
    try:
        N = int(input())
        print(solve(N))
    except:
        break