백준 2331 자바 - 반복수열 (BOJ 2331 JAVA)

문제 : boj2331

 

 

  무작정(brute force) 계속 D[n]을 구해나가면서 이전에 이미 나왔던 결과가 다시 나오는지 확인만 하면 된다. 이 때, 중복된 값은 해싱을 통해 찾으면 빠르게 찾을 수 있다. 추가로 중복값이 나왔을 때 해당값의 위치가 몇번째였는지를 알아야 남게되는 수들의 개수를 출력할 수 있다. 따라서 HashMap을 사용해서 이미 나왔던 수와 해당 수가 몇번째에 나왔는지를 기록해두면 이후 중복된 값이 계산되었을 때 바로 남은 수의 개수를 알 수 있다. (중복값이 나온 위치 이전의 모든 값들이 남은 수들이 된다.)

 

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
    private int getNext(int next, int p) {
        int sum = 0;
        while (next != 0) {
            int digit = next%10;
            int tmp = digit;
            for (int i = 0; i < p-1; i++)
                tmp *= digit;
            sum += tmp;
            next/=10;
        }
        return sum;
    }

    public void solution() throws Exception {
        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());

        HashMap<Integer, Integer> hm = new HashMap<>();
        int cnt = 0;
        int next = a;
        while (!hm.containsKey(next)) {
            hm.put(next, cnt++);
            next = getNext(next, p);
        }
        System.out.println(hm.get(next));
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}