https://www.acmicpc.net/problem/2331
- 예제 입력1
57 2
- 예제 출력1
4
- 문제 접근
- 처음 입력받은 수에서 각 자리마다 P제곱을 하여 모두 더함
- 수열을 계속하여 진행하다보면 반복되는 수열이 등장
- 반복되는 부분을 제외한 반복되지 않은 부분의 개수를 출력하는 문제
- 문제 해결
- 무한대로 저장할 ArrayList 한 개 생성
- 반복된 수를 저장할 반복ArrayList 생성
- 무한 반복 List에서 마지막 값을 뽑아 String으로 받고, 문자열의 길이 만큼 반복
- 0~length-1번까지 charAt() - ‘0’을 하여 정숫값을 저장
- 해당 정수값을 Math.pow() 함수로 P만큼 제곱한 값을 sum에 누적
- 무한 반복 리스트에 포함이 된다면 반복 리스트에 저장
- 단, 반복 리스트에도 포함이 된다면 이미 1번의 루프를 돌았기에 반복문 종료
- list를 Set로 변환하여 중복 제거
- Set에서 반복ArrayList와 겹치는 요소 모두 삭제
- Set의 사이즈 출력
- 슈도 코드
firstNum (처음 수 저장), square (제곱 수 저장)
List list (리스트 선언)
List duplicateList (중복 리스트 선언)
list.add(firstNum)
idx (인덱스로 사용할 변수 선언)
while(무한 반복){
str에 list.get(idx) 저장
sum (누적합 변수)
for(문자열 길이만큼 반복){
num에 str.charAt() - '0' 저장
sum에 num^square 누적
}
if(list에 sum이 포함된다면){
if(duplicateList에 sum 포함된다면)
break
duplicateList에 sum 추가
}
list에 sum 추가
idx 1 증가
}
Set에 list 저장
Set에서 duplicateList가 포함되는 요소 모두 삭제
Set의 size 출력
- 코딩하기
public static void main(String[] args) throws Exception{
Scanner scan = new Scanner(System.in);
int firstNum = scan.nextInt();
int square = scan.nextInt();
List<Integer> list = new ArrayList<>();
List<Integer> duplicateList = new ArrayList<>();
list.add(firstNum);
int idx = 0;
while(true){
String str = list.get(idx).toString();
int sum = 0;
// 각 자리를 square만큼 제곱하여 누적
for(int i = 0; i < str.length(); i++){
int num = str.charAt(i) - '0';
sum += (int) Math.pow(num, square);
}
// list에 포함되는 값이라면
if(list.contains(sum)){
// duplicateList에 포함되는 값이라면 1루프가 돌았으므로 반복문 종료
if(duplicateList.contains(sum)) break;
// 포함되지 않으면 리스트에 추가
duplicateList.add(sum);
}
list.add(sum); // 리스트에 추가
idx++; // 인덱스 1증가
}
// List to Set
Set<Integer> set = new HashSet<>(list);
// set.removeAll(duplicateList)와 동일
duplicateList.forEach(set::remove);
// 사이즈 출력
System.out.println(set.size());
}
'Coding Test > Problem Number' 카테고리의 다른 글
[Java] 칸토어 집합 [4779번] (0) | 2024.07.19 |
---|---|
[Java] 재귀함수가 뭔가요? [17478번] (0) | 2024.07.19 |
[Java] 영식이의 손가락 [2740번] (0) | 2024.07.18 |
[Java] 방 번호 [2740번] (0) | 2024.07.18 |
[Java] 행렬 곱셈 [2740번] (0) | 2024.07.18 |