문제 설명

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

호석이는 불면증에 걸렸다. 그래서 잠이 안 올 때의 민간요법 중 하나인 양 세기를 하려고 한다.

호석이는 1번 양부터 순서대로 세는 것이 재미없을 것 같아서 N의 배수 번호인 양을 세기로 하였다. 즉, 첫 번째에는 N번 양을 세고, 두 번째에는 2N번 양, … , k번째에는 kN번 양을 센다.

이렇게 숫자를 세던 호석이에게 잠은 더 오지 않고 다음과 같은 궁금증이 생겼다. 이전에 셌던 번호들의 각 자리수에서 0에서 9까지의 모든 숫자를 보는 것은 최소 몇 번 양을 센 시점일까?

예를 들어 N = 1295이라고 하자. 첫 번째로 N = 1295번 양을 센다. 현재 본 숫자는 1, 2, 5, 9이다. 두 번째로 2N = 2590번 양을 센다. 현재 본 숫자는 0, 2, 5, 9이다. 현재까지 본 숫자는 0, 1, 2, 5, 9이다. 세 번째로 3N = 3885번 양을 센다. 현재 본 숫자는 3, 5, 8이다. 현재까지 본 숫자는 0, 1, 2, 3, 5, 8, 9이다. 네 번째로 4N = 5180번 양을 센다. 현재 본 숫자는 0, 1, 5, 8이다. 현재까지 본 숫자는 0, 1, 2, 3, 5, 8, 9이다. 다섯 번째로 5N = 6475번 양을 센다. 현재 본 숫자는 4, 5, 6, 7이다. 현재까지 본 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9이다.

5N번 양을 세면 0에서 9까지 모든 숫자를 보게 되므로 호석이는 양 세기를 멈춘다.

[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 N (1 ≤ N ≤ 106)이 주어진다.

[출력]

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 최소 몇 번 양을 세었을 때 이전에 봤던 숫자들의 자릿수에서 0에서 9까지의 모든 숫자를 보게 되는지 출력한다. ( 호석이는 xN번 양을 세고 있다. )

입력

1295

1692

sample_input.txt

출력

#1 10

#2 90

#3 110

#4 6475

#5 5076

sample_output.txt

풀이 과정

문제 그대로 N에 1씩 큰 수를 곱하고, 그 값이 어떤 숫자로 이루어졌는지 추출한 다음, 집합에 넣는 로직을 반복하면 된다고 생각했습니다. 집합에 0~9가 모두 존재한다면 반복을 종료하고 양을 몇 번 셌는지 출력합니다.

주의) 반복 횟수가 아니라 양을 센 횟수(xN번)를 출력해야 합니다.

정답 코드

T = int(input())

for test_case in range(1, T + 1):
    N = input()
    numbers = set(map(int, N)) # 중복되는 값은 무시하기 위해 집합으로 생성
    N = int(N)
    k = 1
 
    while True:
        # 0~9의 숫자가 모두 있으면 반복문 종료
        if numbers == {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}:
            break
        # 곱하는 수 k를 1씩 증가시킨다
        k += 1
        # kN번 양을 센다
        new_N = N * k
        # 각 숫자를 보기 위해 문자열로 변환
        new_N = str(new_N)
        # 이렇게 하면 kN을 이루는 각 숫자를 집합의 형태로 볼 수 있다
        new_numbers = set(map(int, new_N))
        # 두 개의 집합을 합친 집합을 numbers에 넣는다
        numbers = numbers.union(new_numbers)
 
    print("#%d %d" %(test_case, N * k))

이상입니다.

LIST