백준 2526번 파이썬 코드

문제

두 자연수 N과 P를 가지고  다음 과정을 거쳐서 나오는 숫자들을 차례대로 출력해보자. 처음 출력하는 숫자는 N이고, 두 번째 이후 출력하는  숫자들은 N을 곱하고 P로 나눈 나머지를 구하는 과정을 반복하여 구한다. 즉, 먼저 N에 N을 곱하고, 이 수를 P로 나눈 나머지를 두 번째에 출력한다. 다음에는 이 나머지에 N을 곱하고 P로 나눈 나머지를 출력한다. 다음에는 이 나머지에 N을 곱한 후 P로 나눈 나머지를 출력한다. 이 과정을 계속 반복해보면 출력되는 숫자들에는 반복되는 부분이 있다. 

예를 들어서, N=67, P=31인 경우를 생각해보자. 처음 출력되는 숫자는 67이고, 두 번째로 출력되는 숫자는 67×67 = 4489를 31로 나눈 나머지 25이다. 다음에는 25×67 = 1675를 31로 나눈 나머지 1, 다음에는 1×67 = 67을 31로 나눈 나머지 5가 차례대로 출력된다. 다음에는 5×67 = 335를 31로 나눈 나머지 25가 출력되는데, 이 수는 이미 이전에 출력된 수이다. 이 과정을 그림으로 보이면 다음과 같다.

즉 이 과정을 반복하면, 처음 67을 제외하면 3개의 숫자 25, 1, 5가 계속 무한히 반복되게 된다.   또 다른 예로, N=9, P=3을 가지고 시작하면, 9×9 = 81이고 3으로 나눈 나머지는 0이며, 0×3 = 0이고 3으로 나눈 나머지도 0이기 때문에 처음 9를 제외하면 0이 무한히 반복되게 된다. 

N과 P를 입력받아 위와 같이 정의된 연산을 수행하였을 때,  반복되는 부분에 포함된 서로 다른 숫자의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 처음 시작하는 N과 P가 공백을 사이에 두고 주어진다. 단, 1 ≤ N ≤ 1,000, 2 ≤ P ≤ 97이다.  

출력

첫째 줄에 반복되는 부분에 포함된 서로 다른 숫자의 개수를 출력한다.

문제 풀이

먼저 리스트로 각 숫자들이 나타나는 횟수를 기록하고, 그 횟수가 같이 증가하는 것들이 있는지로 한번 해보려고 했었다. 결론부터 말하면 이 접근 방식으로는 풀 수가 없었는데, 카운트가 증가하는 사이클을 살펴보기 위해서 N개가 반복된다고 하면, 내가 살펴봐야 하는 것들이 총 N개다. 그런데 이 N개의 범위가 정해져 있지 않다. 이 말인 즉슨, 메모리도 초과고 시간도 초과될 수 밖에 없다는 것이다.

두번째로 생각한 것은 집합으로 접근하는 방식이다. 집합에 숫자를 집어넣어주고, 집합에 숫자를 집어넣었을 때 집합의 크기가 변하지 않는다면 사이클이 반복될 가능성이 있는 상황이기 때문에 그 때부터 사이클 반복을 감시하는 식으로 접근했다.

사이클 시작할 때는, 첫 숫자 카운트를 1로 초기화해주고, 처음이라는 Flag를 'F'로 만들어주어 계속 감시할 것으로 선언을 했다. 만약 First_Value와 Last_Value가 같은 상황이라면, 사이클의 처음으로 돌아온 것이기 때문에 그동안 세어왔던 카운트에서 1을 뺀 값을 출력하는 식으로 마무리 했다.

import sys
n,p = map(int,sys.stdin.readline().split())
my_set = set()
set_len = len(my_set)
v = n
ff = 'T'
my_cnt = 0

while 1 :
    my_set.add(v)
    if set_len == len(my_set) :
        if ff == 'T' :
            my_cnt = 1
            first_value = v
            last_value = -1
            ff = 'F'
        elif first_value == last_value :
            print(my_cnt-1)
            break
        else :
            last_value = v
            my_cnt +=1
    else :
        ff = 'T'

    v = (v*n) % p
    set_len = len(my_set)