백준 2331번 반복수열(java)

[Silver IV] 반복수열 - 2331

문제 링크

성능 요약

메모리: 14164 KB, 시간: 104 ms

분류

구현, 수학

제출 일자

2024년 8월 3일 18:24:05

문제 설명

다음과 같이 정의된 수열이 있다.

• D[1] = A
• D[n] = D[n-1]의 각 자리의 숫자를 P번 곱한 수들의 합

예를 들어 A=57, P=2일 때, 수열 D는 [57, 74(=52+72=25+49), 65, 61, 37, 58, 89, 145, 42, 20, 4, 16, 37, …]이 된다. 그 뒤에는 앞서 나온 수들(57부터가 아니라 58부터)이 반복된다.

이와 같은 수열을 계속 구하다 보면 언젠가 이와 같은 반복수열이 된다. 이때, 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 구하는 프로그램을 작성하시오. 위의 예에서는 [57, 74, 65, 61]의 네 개의 수가 남게 된다.

입력

첫째 줄에 A(1 ≤ A ≤ 9999), P(1 ≤ P ≤ 5)가 주어진다.

출력

첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다.

풀이

57, 74, 65, 61, 37, 58, 89, 145, 20, 1, 16, 37

 

위와 같은 수열에서 반복 되는 수열을 제외한 나머지 숫자의 개수를 찾는 게 문제이다.

 

필자는 배열과 리스트 중 무엇을 사용할지 고민하다.

 

배열을 너무 크게 초기화 시켜놓는 것이 메모리 낭비라고 생각했기에 리스트를 사용했다.

 

값을 찾을 때마다 리스트를 순회해야 한다는 단점이 있긴 하다.

 

메모리가 부족하다면 리스트를 사용하면 될 것이고, 시간이 부족하다면 배열을 사용하면 될 것이다.

 

풀이는 그냥 수열의 다음 항을 구하고 해당 항이 이미 배열이나 리스트에 존재한다면, 해당 항의 인덱스를 찾아 그대로 출력해주면 끝이다.

전체 코드

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 A = Integer.parseInt(st.nextToken());
        int P = Integer.parseInt(st.nextToken());

        List<Integer> a = new ArrayList<Integer>();
        a.add(A);
        int index = 0 ;
        int  i = 0;
        while(true){
            int s = cal(a.get(i),P);
            if(a.contains(s)){
                index = a.indexOf(s);
                break;
            }

            a.add(s);
            i++;
        }

        bw.write(String.valueOf(index));
        bw.flush();

    }

    public static int cal(int x, int p){
        String s = String.valueOf(x);

        char n[] = s.toCharArray();

        int sum =0;

        for(int i= 0 ;i<n.length;i++){
            sum += (int) Math.pow(Integer.parseInt(String.valueOf(n[i])),p);
        }

        return sum;
    }
}