[백준 7696번 문제, 파이썬3] 반복하지 않는 수

문제

문제

한신이는 어릴 때부터 수에 대한 관심이 남달랐으나 이상하게도 같은 숫자를 두 번 이상 쓰는 것을 굉장히 싫어했다.

그래서 한신이에게 첫 번째 수부터 25번째까지의 수를 적어 보라고 하면

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 23, 24, 25, 26, 27, . . .

과 같이 적어 내었다.

n번째 반복 숫자 없는 수를 만들어 보자!

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스에는 정수 n(1 ≤ n ≤ 1,000,000)이 주어진다. n = 0인 경우 프로그램을 종료한다.

출력

각 테스트 케이스마다 n번째 반복 숫자 없는 수를 출력한다.

---

코드

from itertools import permutations, chain, islice
import math
import sys


def make_no_repeats(length):
    # 0부터 9까지 숫자들로 길이만큼 만들 수 있는 중복되지 않는 순열을 만든다
    my_iter = permutations(range(10), length)

    # 만든 순열 이터레이터에서 islice 메서드로 0이 맨 앞에 오는 경우를 제거하는데
    # 결론적으로 이전에 만들었던 값과 숫자로 볼 때 같은 값을 제거하게 된다

    # 1~9까지 숫자로 1자리 숫자를 만들게 되면 1, 2, 3, 4, 5, 6, 7, 8, 9 라는 순열이 만들어지는데
    # 우리는 0도 사용하면서 반복하지 않는 수를 만들어야한다 그렇게 2자리 숫자를 만들게 되면
    # (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (0, 9), (1, 0), (1, 2), (1, 3),
    # (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9).... 이러한 순열이 만들어진다
    # 9p1은 9이다. 2자리로 만들어진 순열에서 앞에 9개를 지우게 되면
    # (1, 0), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9).... 이러한 순열이 만들어지기 때문이다

    no_zero_start_index = math.perm(9, length - 1)
    
    # 그래서 순열 이터레이터 객체에서 0으로 시작하지 않는 값들로만 잘라서 반환한다.
    no_lead_zeros = islice(my_iter, no_zero_start_index, None)
    
    return no_lead_zeros


if __name__ == '__main__':
    while True:
        count = int(sys.stdin.readline())  # 0을 입력받을 때 까지 반복하면서 입력을 받는다
        if count == 0:
            break

        # 반복하지 않는 수 이터레이터 객체를 만든다. 이터레이터 객체는 실제 값을 갖고 있지 않는다.
        # 백준의 테스트 케이스는 1 <= n <= 1,000,000 이기 때문에 사실은 range(1, 9) 만 해도 된다.
        # 1자리수 부터 9876543210 즉 10자리 까지 반복하지 않는 수를 생성하는 이터레이터 객체의 값들을 자리수마다 만들어서 합친다.
        # 각각의 이터레이터들은 0으로 시작하지 않는 순열을 1자리부터 10자리 까지 있으며 그걸 chain으로 합친다
        iter_no_repeats = chain(*map(make_no_repeats, range(1, 11)))

        # 이터레이터 객체의 n 번째 값을 반환받는다.
        result_number = next(islice(iter_no_repeats, count - 1, None))

        # 반환받은 값은 숫자값들이 튜플 형태로 되어있기 때문에 문자로 만들어서 하나로 합친다
        print(''.join(map(str, result_number)))

 

정답은 아니지만 나름 고민했던 코드... 테스트 케이스대로 답은 나오는데 시간초과 때문에 틀린 코드이다...

참고로 1 ~ 9876543210 까지 반복하지 않는 수의 개수는 8,877,690개이다.

import sys


def make_no_repeat_list(max_count):
    my_list = []
    index = 0
    while len(my_list) < max_count:
        index += 1
        if not len(set(str(index))) < len(str(index)):
            my_list.append(index)

    return my_list


if __name__ == '__main__':
    input_list = []
    while True:
        count = int(sys.stdin.readline())
        if count == 0:
            break
        else:
            input_list.append(count)

    no_repeat_list = make_no_repeat_list(max(input_list))

    for i in input_list:
        print(no_repeat_list[i - 1])

---

해결

이게 실버4 티어라니.. 말도안됨

 

일단 처음 생각했던 방법은 숫자에 같은 숫자가 중복되지만 않으면 될거같아서

숫자를 문자열로 바꾸고 set에 넣은 다음 중복을 제거하고 제거하기 전 길이와 제거 후 길이가 다르면

반복되는 숫자기 때문에

 

그것을 제외하고 만들어지는 반복하지 않는 수를 리스트에 전부 담은

다음 입력되는 n번째 반복하지 않는 수를 인덱스로 접근만 해서

개별로 출력하면 되겠네 싶어서 바로 위 코드대로 했더니 시간초과가 뜨는 것이다

 

간단히 말하면 미리 반복하지 않는 수를 전부 생성 -> n 번째 인덱스만 받아서 접근 후 출력

이렇게 생각했는데 시간초과라니...

 

시간복잡도는 O(n^2) 이긴한데 이것말고는 생각이 안나서 인터넷을 찾아보려고 해도 안나오고

gpt도 이건 어려운지 계속 이건 효율적인 코드입니다만 반복하고 있고

 

결국에는 이틀째 못풀어서 포기하려고 했는데 백준 문제에 원본 출제된곳이 적혀잇었다

 

University > Stanford Local ACM Programming Contest > SLPC 2004 6번

 

저걸 구글에 검색하니까 

 

스택오버플로우에 질문에 답변이 적혀있어서 이걸 해석하기로 했다

 

위 코드는 0부터 9까지 만들 수 있는 순열을 미리 만들어놓는거였다. 사실 반복하지 않는 수가 순열이었는데

이생각을 못했네

 

그러면 숫자로 만들 수 있는 순열은 한자리에서는 0이 최소일거고 최대는 9876543210 일텐데

이걸 어떻게 위 코드에서는 만들었느냐 

 

 

 

0부터 9까지 총 10자리의 수를 가지고 1자리 순열을 만들어보자

0, 1, 2, 3, 4, 5, 6, 7, 8, 9 라는 순열이 만들어질거다

 

문제는 반복하지 않는 수에서 0은 없으니까 0을 제외하고 나머지 수들만 가져가야하는데

9P0은 뭘까 1이다 아무것도 없는 빈 순열 하나만 만들어지기 때문이다

 

그러면 아까 만들었던 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 순열에서 1번째 자리부터 끝까지 가져가면 되지않을까?

그렇게 1, 2, 3, 4, 5, 6, 7, 8, 9 값들을 생성할수있는 이터레이터 객체를 만들었다!!

 

그 다음 이제 두자릿수 순열을 만들어보자

(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (0, 9), (1, 0), (1, 2), (1, 3), .... ,(9, 8)

이러한 순열이 만들어진다

 

9P1은 뭔가 9다 1, 2, 3, 4, 5, 6, 7, 8, 9 라는 순열이란 말이다.

아가 두자릿수 순열의 앞에서부터 9를 제외하면 뭔가?

(1, 0), (1, 2), (1, 3), .... ,(9, 8)이다 그렇게 또 다른 이터레이터 객체를 만들었다!

 

그러니까 만들어지는 순열에서 맨 앞이 0인 경우를 고정하게되면 만들어지는 경우의수는

9P길이-1 과 같다는 뜻이 된다... 이게 원리적으로 왜이렇게 되는지 이해하는게 너무 어려웠다 ㅠㅠㅠㅠ

 

그렇게 만들어지는 이터레이터 객체들을 10개를 합치고 입력받는 N번째 - 1을 합쳐진 이터레이터 객체에서

NEXT로 값을 받게 되면 우리가 답으로 찾아야하는 N번째 반복하지 않는 수를 얻을 수 있다....

 

---

참고

i have a question about this problem. (SLPC 2004 repeatless)

 

주석 없는 버전

from itertools import permutations, chain, islice
import math
import sys


def make_no_repeats(length):
    my_iter = permutations(range(10), length)
    no_zero_start_index = math.perm(9, length - 1)
    no_lead_zeros = islice(my_iter, no_zero_start_index, None)

    return no_lead_zeros


if __name__ == '__main__':
    while True:
        count = int(sys.stdin.readline())
        if count == 0:
            break

        iter_no_repeats = chain(*map(make_no_repeats, range(1, 11)))
        result_number = next(islice(iter_no_repeats, count - 1, None))
        print(''.join(map(str, result_number)))