[코드트리] Cycle - 자바(Java)

문제

https://www.codetree.ai/training-field/search/problems/cycle?&utm_source=clipboard&utm_medium=text

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

 

 

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

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

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

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

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

 

입력 예시

67 31

 

출력 예시

3

 

 

코드

첫 번째 줄에 정수 n과 p가 공백으로 구분되어 주어진다.

• 1 <= n <= 1,000
• 2 <= p <= 97

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int p = Integer.parseInt(st.nextToken());
        br.close();

        // 등장한 수를 담기위한 list
        List<Integer> list = new ArrayList<>();
        list.add(n); // n 담기
        int temp = n; // 연산을 수행할 temp

        while (true) {
            temp = (temp * n) % p; // 사이클 연산

            // 연산된 수가 list에 존재하는지 확인
            if (list.contains(temp)) {
                // 사이클 구하기(list의 크기 - temp의 인덱스)
                int cycle = list.size() - list.indexOf(temp);
                bw.write(String.valueOf(cycle)); // 출력
                break;
            }

            // list에 temp 추가
            list.add(temp);
        }

        bw.flush();
        bw.close();
    }
}