[Java] 1158번. 요세푸스 문제

문제 링크 

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

---

문제 분석

이 문제를 처음 읽었을 때,

이 문제는 완전히 '원형연결리스트(Circular Linked List)'아니야?!라는 생각을 했다.

그런데 Java에서의 LinkedList는 기본적으로 양방향이며,

원형 연결리스트 기능은 지원하지 않는다.

 

자바에서 구현한 연결 리스트의 노드에는

내부적으로 이전과 다음 노드의 주소값을 가지고 있다고 했는데

그냥 이 주소값을 수동으로 바꾸어서

마지막 노드의 다음 노드 주소값에 첫번째 노드의 주소값을 넣으면 되지 않을까?

라는 생각에 열심히 알아보았지만,

Java에서 지원하는 LinkedList의 참조값을 직접 수정할 수 없다고 한다.

 

따라서 문제를 해결 할 수 있는 방안은 크게 다음과 같다.

1. 원형 연결 리스트를 직접 구현한다.

2. 포기하고 그냥 양방향 연결리스트로 해결한다.

 

1번 방법으로 구현을 한다면 다음과 같은 일들을 해줘야한다.

노드 클래스 만들기, add함수 만들기, remove함수 만들기, isEmpty함수 만들기

(여간 귀찮은 일이 아닐 수 없다....)

 

따라서, 시간이 금인 나는 양방향 연결리스트로 이를 해결하고자 했다.

 

예제를 먼저 따져보면,

(7,3)이 <3, 6, 2, 7, 5, 1, 4>로 출력된다는 것은

인덱스로 따지면

2번째 인덱스를 지우고

남은 것 중에 4번째 인덱스를 지우고

남은 것 중에 1번째 인덱스를 지우고

남은 것 중에  3번째 인덱스를 지우고

... 이런 식이다.

 

잘 분석해보면 2씩 뛰어가며, 사람보다 인덱스가 커지면 나머지 만큼을 더 간다.

따라서 index는 (index+k-1)%list.size()와 같다.

 

index에 있는 값을 저장하고, 지우고, 저장하고, 지우고를 반복하면서

list에 저장된 값이 없을 때 까지 반복하면 문제를 해결할 수 있다.

 

---

최종 코드

import java.io.*;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = reader.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int k = Integer.parseInt(input[1]);

        LinkedList<Integer> list = new LinkedList<>();
        for(int i = 1; i <= N; i++){
            list.add(i);
        }

        StringBuilder result = new StringBuilder();

        result.append("<");
        int index=0;
        while (!list.isEmpty()) {
            index = (index + k - 1) % list.size();
            result.append(list.remove(index));
            if (!list.isEmpty()) {
                result.append(", ");
            }
        }

        result.append(">");
        writer.write(result.toString());
        writer.flush();
        writer.close();
        reader.close();
    }
}

 

---

최종 코드 분석

위 코드는 아래와 같은 순서를 따른다.

1. 입력값 받기

2. 리스트 초기화

3. k번째 요소 제거

4. 출력

 

1번은 O(1), 2번은 O(n), 4번도 O(n)의 시간 복잡도를 가진다.

여기서 중요한 것은 3번이다.

 

k번째 요소까지 이동하는데 O(k)시간이 걸리고,

이 것을 모든 요소가 지워질 때 까지, 즉 N번 반복하게 된다.

따라서 시간 복잡도는 O(k*N)이다.

이는 O(N)으로 표현할 수 있다.

 

이 문제 또한 1158번 문제처럼 Stack으로 해결 할 수 있고,

아래 참고 문항에 있는 코드를 참고하면 된다.

---

참고

 

//Stack을 이용한 풀이
import java.io.*;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = reader.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int K = Integer.parseInt(input[1]);

        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();

        for (int i = N; i >= 1; i--) {
            stack1.push(i);
        }

        StringBuilder result = new StringBuilder();
        result.append("<");

        while (!stack1.isEmpty() || !stack2.isEmpty()) {
            for (int i = 0; i < K - 1; i++) {
                if (stack1.isEmpty()) {
                    while (!stack2.isEmpty()) {
                        stack1.push(stack2.pop());
                    }
                }
                stack2.push(stack1.pop());
            }
            if (stack1.isEmpty()) {
                while (!stack2.isEmpty()) {
                    stack1.push(stack2.pop());
                }
            }
            result.append(stack1.pop());
            if (!stack1.isEmpty() || !stack2.isEmpty()) {
                result.append(", ");
            }
        }

        result.append(">");
        writer.write(result.toString());
        writer.flush();
        writer.close();
        reader.close();
    }
}

 

Stack을 이용한 구현 방법은 다음과 같다.

 

1.N과 K를 입력 받는다.

이 때의 시간 복잡도는 O(1)이다.

 

2. 스택을 역순으로 초기화한다.

입력을 N개 받으므로 O(N)이다.

 

3. 모든 요소가 없어질 때 까지(Stack1, 2가 빌 때까지) 아래 과정을 반복한다.

즉, N번 반복한다는 뜻이니 아래 과정의 시간 복잡도에 N을 곱한 것이 최종 시간 복잡도가 되겠다.

 

4. K번째 요소로 접근하는 과정에서 지나치면서 요소들을 Stack2에 넣는다.

즉, K-1번 Stack1에서 Satck2로 push한다.

이 경우 O(K-1)만큼의 시간이 든다.

그러나, Stack1이 비게되어 옮길 수 없다면 Stack2에 있는 내용 모두를 Stack1에 push한다.

그렇게 되면 Stack2에 있던 것들이 Stack1에 역순으로 저장된다.

이 경우, 최악의 경우 N개의 요소를 옮겨야 하므로 시간 복잡도는 O(N)이다.

 

5. K-1번 옮겨간 후 Stack1에 가장 상단에 있는 요소를 출력한다.

출력의 시간 복잡도는 O(1)이다.

 

최종 시간 복잡도를 계산하면,

1+N+N*(K-1+N)+1인데, 가장 큰 수만 따지면

N*(K+N)이다.

 

개인적으로 생각하기에는, 구현 방법도 복잡하고

Stack1이 비면 Stack2에 남은 모든 요소를 Stack1으로 옮겨야 하는 과정이

살짝 번거롭고 비효율적이다고 느꼈다. 

 

항목	LinkedList 이용 코드	Stack 이용 코드
자료구조	LinkedList	두 개의 Stack
시간 복잡도	O(k*N) K와 N이 비슷한 경우 :  O(N^2)	O( N*(K+N) ) K와 N이 비슷한 경우 :  O(N^2)
공간 복잡도	O(N)	O(N)
장점	리스트의 요소에 직접 접근할 수 있다.	스택을 이용하여 요소를 체계적으로 관리할 수 있다.
단점	요소 제거 시 인덱스 계산이 필요하여 remove연산이 비용이 많이 든다. 따라서, 성능이 저하될 수 있다.	요소를 이동시키는 추가 연산이 필요하다.