[백준] 2331번: 반복수열 - JAVA

🔗 문제

BOJ 2331 : 반복수열 https://www.acmicpc.net/problem/2331

💬 풀이

반복수열의 규칙은 입력받은 A부터 시작해 각 자릿수를 P만큼 제곱하여 더한 수로 이어지는 것이다.

최종적으로 반복되는 부분을 제외하고 남는 나머지 수의 개수를 출력해야 한다. 즉, 반복수열의 규칙에 어긋나는 처음 수가 어디까지인지 찾으면 된다.
'어떤 수가 반복되지 않는가'가 아닌, 개수를 찾는 것이 목표이기 때문에 반복되는 구간이 시작되는 인덱스를 찾으면 그 전까지는 우리가 찾고자 하는 수이다.

Integer형 ArrayList에 수열의 규칙에 따라 새로운 수를 추가하고, 반복수열이 다시 시작하는 부분의 인덱스를 출력한다.
새로운 수를 구하는 코드는 nextNum이라는 함수로 구현하여 Math.pow()로 계산한다. 이때, pow()는 double형을 매개변수로 가지므로 형 변환을 해준다.

💻 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int A = Integer.parseInt(st.nextToken());
        int P = Integer.parseInt(st.nextToken());

        ArrayList<Integer> num_arr = new ArrayList<>();
        num_arr.add(A);

        while(true) {
            int new_num = nextNum(A, P);

            if(num_arr.contains(new_num)) {
                System.out.println(num_arr.indexOf(new_num));  // 반복되는 수열의 마지막 인덱스를 출력
                break;
            } 

            num_arr.add(new_num);
            A = new_num;
            // System.out.println(num_arr);
        }
    }
    

    // 수열의 규칙에 따라 숫자를 계산하는 함수
    public static int nextNum(int A, int P) {
        int new_num = 0;
        while(A != 0) {
            new_num += Math.pow(A % 10, (double)P);  // 일의 자리부터 P의 제곱하여 더해나가기
            A /= 10;
        }

        return new_num;
    }
}

📊 정리

✓ 알고리즘 분류 - 수학, 구현
✓ 난이도 - Silver 4

📍 오늘의 메모

• 문제의 예시를 보고 정확히 판단하고 이해할 것
• 처음에는 ArrayList와 HashSet으로 contain 여부를 판단하고 list에서 지우는 등 복잡한 코드로 접근했는데, 이처럼 개수를 구하는 문제에서는 인덱스와 연관지어 생각해보자!

📍 참고 사이트

없음