[BOJ] 백준 1168번 : 요세푸스 문제 2 (JAVA)

문제의 링크 : https://www.acmicpc.net/problem/1168

1168번: 요세푸스 문제 2

문제

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 100,000)

 

비슷한 문제

- 1158번 요세푸스 문제

 

풀이

1158번과 문제는 정확히 똑같지만, 여기서 캐치해야할 부분이 있었습니다. 바로 입력값에서 N과 K가 10만이라는 점이죠.

1158번에서는 Queue로 풀 수 있었지만, 이것은 시간 복잡도가 O(NK)으로 O(10^10)이 되기때문에 Queue로는 해결할 수가 없습니다.

따라서, Queue가 아닌 ArrayList 방식을 이용하기로 하였습니다.

ArrayList를 이용할 때 주의할 점은 문제에서 1~N은 원형이기때문에 ArrayList의 size를 초과할 수 있다는 것입니다. 그러므로, 적절하게 size를 초과할 때는 MOD 연산을 활용하는 것이 관건이었습니다.

자세한 로직은 아래와 같습니다.

1. index = 0부터 시작하여, K - 1만큼 더해준다.

2. 만약, index가 ArrayList의 size보다 크다면 index % size를 취한다.

3. index에 해당하는 요소를 remove한다.

4. ArrayList가 empty 상태가 되면 위 과정을 종료한다.

 

아래는 위 로직을 구현한 소스코드입니다.

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken()) - 1; // index는 0부터 시작하므로 K에  1을 빼준다.
 
        List<Integer> a = new ArrayList<>();
 
        for (int i = 1; i <= N; i++) {
            a.add(i);
        }
 
        int index = 0;
        StringBuilder sb = new StringBuilder();
        sb.append("<");
        for (int i = 0; i < N - 1; i++) {
            index += K;
            
            // index가 size를 초과할 경우 MOD 연산.
            if (index >= a.size()) {
                index %= a.size();
            }
            
            // index에 해당하는 요소를 삭제.
            sb.append(a.remove(index) + ", ");
        }
        // 출력을 편하게 하기 위하여 마지막 요소는 따로 빼서 삭제.
        sb.append(a.remove(0) + ">");
 
        bw.write(sb.toString() + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

 

추가 사항

위 소스코드를 보면, 바깥 쪽 for문에서 N번 반복하므로 시간 복잡도가 O(N)이고, ArrayList이 remove method는 시간 복잡도가 O(N)으로 알려져있습니다. 따라서, O(N^2)이라 생각하여 위 소스코드는 돌아가지 않을 것으로 예상되지만 실제로 통과되는 것을 알 수 있습니다.

다른 분에게 질문을 해 보니, ArrayList의 remove 연산이 단순히 메모리 위치를 앞으로 당기면 되는 것이기때문에 굉장히 빠르다는 답변을 받았습니다.

그렇다면, 위 답변에 의하면 이 문제에서는 그냥 O(N)이 아닌 매우 빠른 O(N) 수준으로 작동한다는 것인데 여기서 의문점이 하나 들었습니다.

제가 구글에서 이것저것 뒤져 본 문서에서는 시간 복잡도가 O(N)으로 나와있는데, 이것이 매우 빠른 O(N)을 나타내는 것인지, 아니면 평균적인 것을 나타내는 것이 알 수 없었습니다.

만약, 후자라면 어떠한 경우에 평균적으로 O(N)이고, 어떠한 경우에 매우 빠르게 위 소스코드가 통과될 정도로 빠른 O(N)을 나타내는 것인지는 아직 의문인 상태입니다.

추후에 더 많은 조사를 통해 알게 된 정보를 다시 이 게시글에 써놓도록 하겠습니다. 그리고 이것과 관련하여 의견이 있으신 분들은 댓글로 자유롭게 남겨주시면 감사하겠습니다.

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.