백준 6523 요세푸스 한 번 더! - JAVA

6523 문제 링크

---

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

 

문제 설명

---

 

입출력

---

 

코드

---

import java.io.*;
import java.util.*;
 
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));
        HashMap<Integer, Integer> visitCount = new HashMap<>();
        
        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            if (N == 0) break;
 
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int x = 0, totalCount = 1;
 
            while (true) {
                if (x == 0) {
                    x = b % N;
                } else {
                    x = (int) (((1L * a * x % N) * x % N + b) % N);
                }
                if (visitCount.containsKey(x)) {
                    bw.write(String.valueOf(N - (totalCount - visitCount.get(x))));
                    bw.newLine();
                    visitCount.clear();
                    break;
                } else {
                   visitCount.put(x, totalCount++);
                }
            }
        }
        bw.flush();
    }
}

 

트러블 슈팅🚀

---

해당 문제는 사이클의 개념을 정확히 이해하고 있어야 하는 문제로, 겉보기에는 간단해 보이지만 막상 풀어보면 쉽지 않은 문제였습니다. 풀릴 듯 말 듯하면서도 끊임없이 메모리 초과가 나는 부분이 많았고, 결국 해결하는 데만 4시간이 넘게 걸린 애증의 문제입니다. ㅎㅎ

또, 모듈러 연산과 업캐스팅을 적절하게 조합하여, 정답을 찾아야하는 문제입니다.

문제를 해결하고 나서, 해당 문제관련 풀이들을 서치를 해봤는데, 거의 찾을 수 없었고, 자바로 이 문제를 포스팅하는건 아마... 제가 처음이지 않을까 싶습니다.

 

처음 이 문제를 접했을 때, 시작점(x = 0)에서 시작하여 수식 번호선택규칙(ax^2 + b mod N)에 맞추어 값을 계산해 나갔습니다.

getOrDefault() 메서드를 사용해 각 key(선택된 사람의 번호) 에 대해 value(선택된 횟수) 를 저장하면서 진행했습니다.

• 특정 번호가 선택될 때마다 value 값을 증가시키고,
• value가 2가 된 경우 총 술을 마신 사람의 수인 totalCount를 증가시켰습니다.
• 이를 무한히 반복하면서 선택된 key의 value가 3이 되는 순간, 즉 한 사람이 세 번째 선택되는 경우 루프를 종료하고,
• 원탁에 앉은 인원 수 - totalCount(술을 마신 사람의 수) 를 반환하는 방식으로 문제를 해결하려고 했습니다.

그러나 이 풀이방식은 메모리의 크기를 고려하지 못한 풀이였습니다. 잘못된 풀이와 해당 풀이의 사이클 계산과정을 비교해보겠습니다.

먼저 로직은 맞지만, 메모리를 초과하는 코드와 함께 사이클 계산 과정 비교 그림을 살펴보겠습니다.

 

< 메모리 초과 코드 > - 값 도출은 정상적으로 수행됨!

// 메모리 초과 코드
import java.io.*;
import java.util.*;

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));
        Map<Integer, Integer> visitCount = new HashMap<>();
        
        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            if (N == 0) break; // 입력 종료 조건
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            // 각 사람의 선택 횟수를 저장하는 맵
            int x = 0; // 시작점: 첫 번째 사람
            int totalDrink = 1; // 술을 마신 사람 수

            while (true) {
                // 현재 사람의 선택 횟수 증가
                visitCount.put(x, visitCount.getOrDefault(x, 0) + 1);
                if (visitCount.get(x) == 3) { // 선택 횟수가 3번이면 종료
                    visitCount.clear();
                    break;
                }
                if (visitCount.get(x) == 2) { // 선택 횟수가 2번이면 술을 마신 사람으로 카운트
                    totalDrink++;
                }
                // 다음 번호 계산
                x = (int) (((1L * a * x % N) * x % N + b) % N);
            }
            // 술을 마시지 않은 사람의 수는 전체 인원 - 술 마신 사람 수
            bw.write(String.valueOf(N - totalDrink + 1));
            bw.newLine();
        }
        bw.flush();
    }
}

---

< 사이클 계산 과정 비교 >

getOrDefault() 방식과 containsKey() 방식의 차이를 살펴보면, 연산 블록의 수에서 명확한 차이가 발생하는 것을 알 수 있습니다. getOrDefault() 방식은 2번의 사이클을 돌며, 첫 번째 사이클에서 키의 존재 여부를 확인하고, 두 번째 사이클에서 사이클의 범위를 계산하는 과정을 거칩니다. 반면, containsKey() 방식은 키의 존재 여부를 확인하는 1번의 사이클만으로 사이클의 범위를 계산하므로, 상대적으로 적은 연산을 수행합니다. 따라서, containsKey() 방식이 더 적은 연산을 필요로 하게 됩니다.

또한, HashMap은 객체만을 저장할 수 있으므로, getOrDefault() 방식은 캐싱되지 않은 범위의 정수에 대해 새로운 Integer 객체를 생성하게 되어, 사이클 $C$에 대해 대략 $2C$개의 Integer객체를 생성하게 되어, 메모리 사용량이 늘어날 수 있습니다. 반면, containsKey() 방식은 추가적인 객체 생성을 피할 수 있어 $C$개의 Integer객체만을 생성하게 되므로, 데이터 셋 크기가 클수록 메모리 사용량과 성능 면에서 유리합니다.

따라서, 성능 최적화를 위해 containsKey() 방식을 사용하는 것이 더 효율적일 수 있습니다.

 

💡Integer의 자동 캐싱
Integer 자동 캐싱은 자바에서 Integer 객체가 특정 범위 내에서 재사용되는 기능입니다. 자바는 성능 최적화를 위해, -128부터 127까지의 범위 내의 Integer 객체를 자동으로 캐싱합니다. 즉, 이 범위에 해당하는 Integer 값은 새로운 객체를 생성하지 않고, 이미 만들어진 객체를 재사용합니다.

 

알고리즘 설명

---

해당 문제에서 메모리 초과를 제외하고도, 연산의 정확성 즉, 오버플로우 방지를 위해 모듈러 연산을 짚고 갈 필요가 있겠습니다. 모듈러 연산(%)의 핵심은 수식에 분배법칙을 적용하는 것으로 곱셈의 분배법칙과 동일하게 작용합니다. 즉,

$$(a \times x^2 + b) \mod N$$

↓

$$(((a \times x \mod N) \times x) \mod N + b) \mod N$$

위와 같이 모듈러 연산의 성질을 적용할 수 있습니다. 다만, 연산 과정에서 x의 제곱을 계산할 때 int 자료형의 범위를 초과할 가능성이 있습니다. 이를 방지하기 위해, 연산의 첫 단계에서 1L을 곱해 long 타입으로 변환한 후, 모든 연산을 long 범위 내에서 수행한 뒤 int로 다운캐스팅하는 것이 안전합니다.

 

코드 해석

---

입력으로 N, a, b 값을 받습니다. N == 0이면 프로그램을 종료합니다.

 

처음 선택된 사람의 번호 x는 0이며, totalCount를 1로 설정합니다.

첫 번째 선택은 x가 0이므로 b % N으로 결정되며, 이후 선택은 ((1L * a * x % N) * x) % N + b) % N 를 이용해 계산됩니다.

각 사람이 선택된 횟수는 visitCount 맵에 저장하면서 진행하고,

만약 이미 선택된 번호가 HashMap에 존재한다면, 처음 선택된 위치를 이용해 사이클을 계산하고,

술을 마시지 않은 사람의 수를 N - (totalCount - visitCount.get(x))로 구합니다.

결과를 출력한 후, 다음 테스트 케이스를 위해 맵을 초기화합니다.

 

입력이 끝날 때까지 위 과정을 반복하며 결과를 출력합니다.