[CodeTree/Python] Cycle

문제

Cycle

숫자 N과 P가 주어집니다.

처음에는 N으로 시작합니다.

다음에는 그 숫자에 N을 곱하고 P로 나눈 나머지를 구합니다.

이 행동을 반복하면 언젠가는 이미 등장했던 숫자가 등장하게 됩니다.

이 때에 반복되는 사이클의 크기를 구하는 프로그램을 작성해보세요.

 

입력 형식

첫번째 줄에 N과 P가 공백을 사이에 두고 주어집니다.

• 1 ≤ N ≤ 1,000
• 2 ≤ P ≤ 97

출력 형식

첫번째 줄에 반복되는 사이클의 숫자 개수를 출력하세요.

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

풀이

n, p = map(int, input().split())
li = [n]
count = []
seen = {}
while li:
    num = li.pop()
    remain = (num * n) % p
    count.append(remain)

    if remain in seen:
        start = seen[remain]
        length = len(count) - start
        break

    li.append(remain)
    seen[remain] = len(count)

print(length)

BFS만 보다가 숨통이 좀 트인다...

1. n, p를 차례로 입력받는다.
2. 반복할 스택(li), 나머지를 받을 리스트(count), 중복을 확인할 딕셔너리(seen)를 생성한다.
3. 스택에서 값을 꺼내고, 계산한 나머지(remain)를 리스트에 넣어준다.
   동시에 같은 값을 스택에 넣는다. 이 때 나머지 값을 key로 가지는 딕셔너리의 value는 나머지 리스트의 길이이다.
4. 만약 나머지 값이 딕셔너리에 존재한다면, 반복되는 나머지에 해당하는 인덱스의 등장 길이를 시작 위치로 지정한다.
   즉, 길이는 전체 나머지를 받은 리스트의 길이에서 시작 위치(길이)를 제한 값이며, 반복문을 빠져나간다.