[백준] 요세푸스 한 번 더! JAVA

반응형

728x90

[백준] 요세푸스 한 번 더! - GOLD II 6523번

---

접근

• map

---

풀이

오랜만의 백준 문제인데 팀원이 재밌다고 공유해 준 문제이다. N명의 사람이 원탁에 앉아 수식을 통해 다음 술 마실 사람을 정하고 똑같은 사람이 3번 걸렸을 때 술자리가 종료되는데 그때 술을 마시지 않았던 사람의 수를 구하는 문제이다. 

 

문제 내용만 보면 정말 쉬워 보이는데 재밌을 거라는 뜻이 처음엔 뭔지 몰랐으나 알게 되었다. 로직은 정말 간단하게 map을 사용해 술 마신 사람과 횟수를 저장하고 3번이 되면 술 마신 사람들 수를 전체 인원에서 빼면 구할 수 있을 거 같았다. 다만 사람의 수가 최대 10의 9 제곱으로 10억 명까지 존재가 가능하기 때문에 다음 술 마실 사람의 번호를 구하는 ax^2+b mod N 이 수식에서 오버플로우가 발생할 테니 그 부분을 신경 쓰는 문제인 줄 알았다. 

 

백준은 입력으로 들어오는 값을 직접 받아 파싱 해줘야 하기 때문에 입력은 받았다 생각하고 핵심 로직 코드부터 보겠다.

    private static int solution(int n, int a, int b) {
        Map<Integer, Integer> counts = new HashMap<>();
        int current = 0;
        int result = n;

        while (true) {
            counts.merge(current, 1, Integer::sum);

            if (counts.get(current) == 2) {
                result--;
            } else if (counts.get(current) == 3) {
                break;
            }

            current = calculate(current, a, b, n);
        }

        return result;
    }

정말 간단한 코드로 맵에 사람과 술 마신 횟수를 저장하고 3번이 되면 종료하는 형태이다.

    private static int calculate(int current, int a, int b, int n) {
        long x2 = ((long)current * current) % n;

        long ax2 = ((long)a * x2) % n;

        return (int)((ax2 + b) % n);
    }

신경 썼던 다음 번호를 구하는 연산으로 오버플로우가 발생하지 않게 long 타입 사용과 중간중간 모듈러 연산을 추가해 오버플로우가 날 수 없게 처리해 줬다. 

 

문제는 다른 곳에서 발생했다.

메모리 제한: 128MB

메모리 초과가 발생했다. 문제의 입력에선 사람의 수가 최대 10의 9 제곱인 10억 명까지 존재한다고 했지만 첫 사람이 술을 마시기 위한 단계의 수는 10의 6 제곱보다 작다고 나와있어 결국 첫 사람에서 시작해 다시 첫 사람이 술을 마시게 되는 사이클의 길이가 10의 6 제곱보다 작다는 뜻이고 그 말은 map에는 최대 10의 6 제곱개의 요소가 들어가게 된다는 뜻인데 대략적으로 계산해 본 경우 48~64MB로 메모리 제한인 128MB에 비해 충분한 수치이다.

 

하지만 메모리 초과가 떴으니 다른 방법을 생각해 봤는데 사이클을 구한다 해도 사이클에 포함된 사람을 다 보관해야 한다. 그 말은 사이클을 구한다 해도 반복 횟수만 줄일 수 있지 결국 저장하게 되는 요소의 개수 자체는 동일해 똑같이 메모리 초과가 날 테니 수식화해서 구해야 하는 건가 생각하던 찰나에... 

 

팀원 중 한 명이 풀었다고 했고 map을 사용했다고 했다. map을 사용했다는 건 아무리 생각해도 요소를 저장했다는 거 같은데 그렇다면 어떻게 메모리 초과가 안 난 건지 이해가 가지 않았는데 다른 사이트들과 백준의 다른 점이 생각이 났다. 다른 사이트들은 보통 코드를 완성하면 완성된 코드를 기준으로 각 테스트케이스에 대해 독립적으로 수행을 해준다.(아마도?) 독립적으로 수행이 되다 보니 한 케이스당 새로운 메모리에서 동작한다고 생각한다. 그러나 백준의 경우 입력으로 여러 케이스가 들어오게 되고 한 번의 프로그램 실행 시 모든 케이스의 결과를 다 출력해야 정답으로 인정된다. 그 부분에서 128MB 메모리에서 프로그램이 실행되었다고 가정하에 이전 케이스에서 map으로 할당되었던 공간에 값이 비워진다 해도 다음 케이스를 위한 map이 연속적으로 할당할 공간이 부족할 때 메모리 초과가 발생하는 것이 아닌가 싶었다. 

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while(true) {
            String readLine = br.readLine();
            if(readLine.equals("0")) break;

            String[] input = readLine.split(" ");

            int n = Integer.parseInt(input[0]);
            int a = Integer.parseInt(input[1]);
            int b = Integer.parseInt(input[2]);

            System.out.println(solution(n, a, b));
            System.gc();	// 가비지컬렉터 호출
        }
    }

단편화된 메모리에서 할당할 공간을 찾지 못해 메모리 초과가 발생한 것으로 한 케이스가 끝날 때마다 가비지컬렉터를 직접 호출해 가비지컬렉션을 수동으로 수행해 주었다. 

가비지컬렉터 호출

문제 자체의 내용은 정말 쉬운데 왜 골드2인지 알게 되는 느낌이었다. map을 static으로 선언해서 썼다면 조금 더 메모리 사용과 시간을 줄일 수 있다.

---

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while(true) {
            String readLine = br.readLine();
            if(readLine.equals("0")) break;

            String[] input = readLine.split(" ");

            int n = Integer.parseInt(input[0]);
            int a = Integer.parseInt(input[1]);
            int b = Integer.parseInt(input[2]);

            System.out.println(solution(n, a, b));
            System.gc();
        }
    }

    private static int solution(int n, int a, int b) {
        Map<Integer, Integer> counts = new HashMap<>();
        int current = 0;
        int result = n;

        while (true) {
            counts.merge(current, 1, Integer::sum);

            if (counts.get(current) == 2) {
                result--;
            } else if (counts.get(current) == 3) {
                break;
            }

            current = calculate(current, a, b, n);
        }

        return result;
    }

    private static int calculate(int current, int a, int b, int n) {
        long x2 = ((long)current * current) % n;

        long ax2 = ((long)a * x2) % n;

        return (int)((ax2 + b) % n);
    }
}