[SWEA 3809번_Python] 화섭이의 정수 나열_in keyword, find 메소드

 

풀이에 대해 리뷰하기 전에... 코딩테스트 리뷰를 하나 하나 올리다보니 블로그 포스팅하기에는 너무 많아 글쓰다가 지치는 나의 모습을 보고 정말 중요한 문제만 포스팅하려고 했는데... 이 문제 풀이에 1시간 가까이 걸렸는데... 다른 분들의 풀이를 보니 제 자신에 너무 화가나 개선된 풀이와 추가적인 풀이까지 덧붙여 포스팅해봅니다. ㅎㅎ

이러면서 크는거겠죠... 모...

 

주소: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWHz7xD6A20DFAVB 

SW Expert Academy

[ 문제 ]

문제 ※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다. 화섭이는 다음과 같은 흥미로운 추측에 대해 들었다. “모든 정수는 π = 3.14159265…의 어떤 연속한 부분으로 나타난다.” 화섭이는 π에 대해 이것을 테스트해 보기는 힘들다고 생각했고, 그냥 유한한 정수열에 대해서 위처럼 연속한 부분을 끊어내어 보았다. 예를 들면 “3 0 1”같은 정수열로는 3, 0, 1, 30, 301을 만들 수 있다. 화섭이는 주어진 정수열로 만들 수 없으면서 가장 작은 정수가 무엇인지 궁금해졌다. 이를 구하는 프로그램을 작성하라. 위의 예에서는 0, 1은 나타나지만 2는 나타나지 않으므로 2가 답이 된다. 두 번째 테스트케이스를 예로 들면, 위 그림과 같이 0부터 11까지의 정수는 만들 수 있으나 12를 만들 수 없다. 그러므로 12가 답이 된다. 입력 첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 N(1 ≤ N ≤ 103)이 주어진다. 다음으로는 N개의 정수 d1, d2, …, dN (0 ≤ di ≤ 9)이 순서대로 주어진다. d들은 공백 하나 또는 줄바꿈으로 구분되어 있다. 출력 각 테스트 케이스마다 만들어낼 수 없는 가장 작은 정수를 출력한다.

 

[ 나의 귀여운 풀이 ]

풀이 1 - 완전탐색 이용

T = int(input())

for test_case in range(1, T + 1):
    N = int(input())
    numbs = []
    result = -1
    arr = set()
    
    while len(numbs) != N:
        numbs.extend(list(input().split()))

    for i in range(1, N+1):
        tmp = ""
        for j in range(0, N-i+1):
            tmp = "".join(numbs[j:j+i])
            arr.add(int(tmp))
        for k in range(0, 10**i):
            if k not in arr:
                result = k
                break

        if result != -1:
            print(f"#{test_case} {k}")
            break

결과적으로 PASS한 풀이긴 하지만 코드 길이도 길고 긴 코드를 짜려다 보면 버그 확률이 높아지고 버그 확률이 높아지면 디버깅하느라 시간이 부족하고... 주저리 주저리 악순환이 벌어진다... 완전탐색으로 1자리 수 -> N자리 수를 모두 구해서 해결하려고 했다.

 

하지만 그렇게 하다보면 문제점이 생긴다.

 

N자리 수를 모두 구하려면 1 ~ 1000자리 수까지 구해야한기 때문에 시간, 공간적 비용이 어마어마하다. 제한 시간, 공간 조건을 못 맞출 수 있다.(그래서 모두 구하는 것은 실질적으로 불가능하기 때문에 10 * N자리수 마다 break check point를 뒀지만, 테스트케이스에 어마어마한 자리수의 숫자가 있었다면 Fail했을 것이다.)

 

풀이 2 - 'a' in "string"(in keyword 이용!)

T = int(input())

for test_case in range(1, T + 1):
    N = int(input())
    li = []

    while len(li) != N:
        li += list(input().split())

    li = "".join(li)

    for i in range(1000):
        if str(i) not in li:
            break

    print(f"#{test_case} {i}")

input을 통해 받아온 입력들을 하나의 String으로 만들어준다.

그 후 1 ~ 1000까지의 연속된 숫자가 String의 Substring으로 존재하는지 여부를 in keyword를 통해 판별하고 있다.

 

이렇게 문제를 풀고나니 새로운 풀이가 생각이 났다...

 

str.find() 메소드를 사용하는 것이다.

 

풀이 3 - str.find() 메소드 사용

T = int(input())

for test_case in range(1, T + 1):
    N = int(input())
    li = []

    while len(li) != N:
        li += list(input().split())

    li = "".join(li)

    for i in range(1000):
        if li.find(str(i)) == -1:
            break

    print(f"#{test_case} {i}")

find 메소드를 사용하는 방법도 있다!

 

 

[ 개인적인 만족도 ]

(수달 1~5마리)

수달: 4.5마리! 어려운 풀이더라도 열심히 결국 풀어낸 점에서 나를 칭찬한다.

아쉬운 점: 기본 메소드나 키워드를 사용하는 방법도 있다.

이런 부분을  추가적으로 공부하는 것도 좋을 것 같다.

 

 

꾸준히 열심히!