SWEA 1288. 새로운 불면증 치료법

내가 첫번째로 푼 방법

답이 나오기 했지만, 제한 시간 초과가 되었다.
그래서 시간복잡도를 생각해보니, N² 의 복잡도가 나온다고 생각되었다.
이유는 while 문k에 자연수를 계속 곱할 때마다 digits 배열을 탐색하고,
while 문 안에서 또 한번 kN의 자릿수 만큼 탐색하게 탐색하게되므로 N² 의 복잡도 가 나온다고 생각했다.

for test_case in range(1, T + 1):
    n = int(input())
    digits = [ 0 ] * 10;
    
    answer = 1
    while 0 in digits:
        kn =  str(n * answer)
        for i in kn:
            nth = int(i) -1
            if digits[nth] == 0:
                digits[nth] = 1
                answer+= 1
    print(answer)
      

새로 푸는 방법

그렇다면, 탐색을 적게해야되지 않을까라는 생각을 하게 되었다.

그래서 while 의 조건에서 탐색하지 않도록 하기 위해 while(True)로 변경.
while 문 안에서 탐색을 2번 각각 독립적으로 하도록 만들었다.

for test_case in range(1, T + 1):
    n = int(input())
    digits = [ 0 ] * 10;
    
    answer = 1
    while True:
        kn =  str(n * answer)
        for digit in kn:
            if digits[int(digit)] == 0:
                digits[int(digit)] = 1
        answer += 1
        if 0 not in digits:
            break;
    print("#%d %d" % (test_case, answer))
      

이번에는 시간이 통과되었으나, 답이 맞지 않았다.
그래서 문제를 다시보니 "숫자를 센 횟 수가 아니라, 0~9 까지 모두 나오게 되는 수를 원하는 거였으므로,
다음과 같이 고쳤다.

for test_case in range(1, T + 1):
   
    n = int(input())
    digits = [ 0 ] * 10;
    cnt = 1
    while True:
        kn =  str(n * cnt)
        for digit in kn:
            if digits[int(digit)-1] == 0:
                digits[int(digit)-1] = 1
        if 0 not in digits:
            break
        cnt += 1
    answer = n * cnt
    print("#%d %d" % (test_case, answer))
    ```