[Python, 파이썬] SWEA 3809. 화섭이의 정수 나열

주어진 정수열로 만들 수 없으면서 가장 작은 정수를 구하는 문제.

예) 위와 같은 정수가 주어질 때, 주어진 문자열로 만들 수 없는 가장 작은 수는 12!

 

 

def find(A):

    number = ''.join(A) # 문자열로 변환

    for i in range(int(number)): # number 수만큼 반복
        if(str(i) not in number): # number 안에 없으면
            return i # 없는 수 return

T = int(input()) # 테스트케이스의 개수 T

for test_case in range(1, T+1):

    N = int(input()) # 숫자 N

    A = [] # 정수 N개

    # 주어진 개수 만큼 입력 받음
    while len(A) < N:
        A.extend(input().split())

    answer = find(A) # 없는 수 찾기
    print("#%d %d" %(test_case, answer)) # 정답 출력  

 

 

 

[문제풀이]

---

 

처음엔 이 문제, 입력부터 난관이였다.

3 6 7 5 3 5 6 2 9 1 2 7 0 9 3 6 0 6 2 6
1 8 7 9 2 0 2 3 7 5 9 2 2 8 9 7 3 6 1 2
9 3 1 9 4 7 8 4 5 0 3 6 1 0 6 3 2 0 6 1
5 5 4 7 6 5 6 9 3 7 4 5 2 5 4 7 4 4 3 0
7 8 6 8 8 4 3 1 4 9 2 0 6 8 9 2 6 6 4 9

 

입력의 for문을 돌리는 숫자가 정해진 게 아니라 줄바꿈 문자로 구분되어 있고, 그걸 정해진 개수가 입력받을 때까지 계속 입력받아야 한다.

while len(A) < N:
        A.extend(input().split())

 

그래서 이렇게 N의 개수가 될때까지 계속 while문을 돌려 입력받게 하였다.

그 후 주어진 문자열에서 연속된 부분으로 만들 수 없는 가장 작은 수를 찾았다.

 

처음엔 set으로 모든 조합을 찾는 걸로 하였지만 이건 시간초과가 난다....

시간 복잡도 내론 충분히 가능할 거 같았는데, 왜인진 모르겠다.

for i in range(int(number)): # number 수만큼 반복
        if(str(i) not in number): # number 안에 없으면
            return i # 없는 수 return

 

그래서 다른 분 코드를 좀 참고하여, for문을 돌려 문자열에서 포함 여부를 확인하는 in 메소드를 사용해 있으면 그 수를 return하는 방식으로 찾았다.