Menu

Subscribe

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

HEESOO on Boj

👀 문제

https://www.acmicpc.net/problem/2331

👊 도전

1. 설계

  1. 문제대로 코드를 짠다.
  2. 현재 숫자 num의 각 자리수에 p제곱한 값이 이전에 나온 값인지 확인하기 위해 HashSet을 이용한다.
  3. HashSet에 숫자들을 넣고 중복 체크한다.
  4. 숫자들의 순서를 체크하기 위해 ArrayList를 이용한다.
  5. 중복 숫자가 나오면 list에서 해당 숫자 인덱스를 리턴하면 된다.

2. 구현 (성공 코드)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

import java.util.*;
import java.io.*;
/**
 * @author HEESOO
 *
 */
class Main {
	public static void main(String[] args) throws IOException {
		Scanner sc=new Scanner(System.in);
		
		int a=sc.nextInt();
		int p=sc.nextInt();	
		ArrayList<Integer> list=new ArrayList<>(); // 숫자 순서대로 저장
		HashSet<Integer> set=new HashSet<>(); // 숫자 중복 체크
		list.add(a);
		set.add(a);
		
		while(true) {
			int num=makeNum(a, p); // 다음 숫자 계산
			if(set.contains(num)) { // 반복 찾음
				System.out.println(list.indexOf(num));
				break;
			}
			// 새로운 숫자일 경우 set, list에 add
			set.add(num);
			list.add(num);
			a=num;
		}
	}
	
	public static int makeNum(int a, int p) {
		int sum=0;
		while(a>0) {
			sum+=Math.pow(a%10, p);
			a/=10;
		}
		
		return sum;
	}
}

3. 결과

실행결과 🤟 성공 🤟

4. 설명

  1. 수열을 구한다
    • 새로운 숫자가 나오는지 체크해야하므로 HashSet을 이용한다.
    • HashSet에 숫자들을 저장해놓고 중복 체크한다.
    • 숫자들의 순서도 중요하다. 따라서 ArrayList를 이용한다.
    • 다음 숫자(num)는 makeNum()을 이용해서 구한다.
    • set에서 num이 있는지 체크한 후, 있다면 반복 구간을 찾은 것이므로 list에서 해당 인덱스를 리턴한다.
    • 없다면 아직 반복 구간이 아니므로 set, list에 넣는다.

👏 해결 완료!

참고