[프로그래머스] 요세푸스 문제

1. 문제

---

2. 풀이 과정

---

처음엔 그냥 무작정 리스트에 1~N까지 넣어놓고 넣다 뺐다 했다.

하지만 이렇게 하면 코드가 상당히 복잡해진다... 

 

리스트로 구현 했을 때 가장 어려웠던 점은 기준이 되는 사람과 삭제될 사람의 위치 차이였다. 

리스트는 선형으로 구성되어 있기 때문에 끝쪽 인덱스에 있는 사람이 기준이 되면 삭제할 사람을 찾을 때 다시 리스트 처음으로 돌아와 삭제할 사람을 찾아야 한다.

말로만 들으면 그냥 나머지 연산으로 해결하면 될 것 같지만 막상 구현해보니 따져야할 케이스가 많았고 이로인해 코드가 상당히 복잡해졌다.

 

---

그래서 리스트를 재구성해 삭제될 사람이 항상 리스트의 맨 앞에 위치하게 끔 하는 건 어떨까 생각했다. 

1. 기준이 되는 사람을 리스트에 제일 앞에 오게 해서 이 사람부터 하나씩 삭제하고 다시 맨 뒤로 저정한다.
2. 이러한 과정을 삭제할 사람이 리스트의 맨 앞에 올 때까지 반복한다.
3. 그 사람을 삭제한다.
4. 그 사람이 삭제되면 자연스럽게 맨 앞에 기준이 되는 사람이 온다.

이러한 과정은 그냥 리스트로도 해결할 수 있겠지만 나는 큐로 해결했다. 

리스트로 해결하게 되면 remove() 하는 과정에서 O(N) 만큼의 시간복잡도가 발생한다.

반면 큐는 반드시 제일 먼저 들어간 데이터만을 삭제하므로 O(1)의 시간복잡도가 발생한다.

이 상황에서는 항상 삭제는 맨 앞 데이터 즉, 제일 먼저 들어간 데이터에 대해서만 일어나므로 큐를 사용하는 것이 효율적이다.

 

그림으로 보면 다음과 같다.

N = 5, K = 2라면

• 최초 기준은 1번 사람이다.

• 2번째 사람을 찾기 위해 기준이 됐던 1을 큐에서 꺼내 뒤에 넣었다. (이 과정은 K-1번 반복돼야 함)
• 이렇게 되면 삭제 될 사람인 2가 맨 앞으로 오게 된다.

• 다음 기준은 삭제됐던 사람의 다음이므로 자연스럽게 기준이 되는 사람은 큐의 맨 앞에 위치한다.

• 다시 2번째 사람을 찾기위해 기준이 됐던 3을 큐에서 꺼내 맨 뒤로 넣었다.
• 이렇게 되면 삭제 될 사람인 4가 맨 앞에 오게 된다.

• 다음 기준은 삭제됐던 사람의 다음이므로 자연스럽게 기준이 되는 사람은 큐의 맨 앞에 위치한다.

• 다시 2번째 사람을 찾기위해 기준이 됐던 5를 큐에서 꺼내 맨 뒤로 넣었다.
• 이렇게 되면 삭제 될 사람인 1이 맨 앞에 오게 된다.

• 다음 기준은 삭제됐던 사람의 다음이므로 자연스럽게 기준이 되는 사람은 큐의 맨 앞에 위치한다.

• 다시 2번째 사람을 찾기위해 기준이 됐던 3을 큐에서 꺼내 맨 뒤로 넣었다.
• 이렇게 되면 삭제 될 사람인 5가 맨 앞에 오게 된다.

• 3이 최종적으로 큐에 남게 되므로 답은 3이된다.

 

3. 내 코드

---

public static int solution(int N, int K) {
    Queue<Integer> queue = new ArrayDeque<>();

    for(int i = 1; i <= N; i++) {
        queue.add(i);
    }

    while(queue.size() > 1) {
        for(int i = 0; i < K - 1; i++) {
            Integer poll = queue.poll();
            queue.add(poll);
        }

        queue.poll();
    }

    return queue.poll();
}

시간복잡도

• O(N X K) (N: 사람 수, K: 없앨 사람의 순서)

코드는 매우 간단하다.

4. 피드백

---

• 배열을 재구성할 때 큐를 사용하는 것도 좋은 방법인 것 같다.