[코딩 테스트 Java] 큐 ❷

이 글은 〈[되기] 코딩 테스트 합격자 되기(자바 편)〉에서 발췌했습니다.

골든래빗 출판사
김희성, 박경록 지음

큐 개념을 이해하고, 이를 바탕으로 ADT를 작성할 수 있습니다.

[코딩 테스트 Java] 스택 ❷ – 몸풀기 문제

지금까지 배운 내용을 활용해서 문제를 풀어보겠습니다. 여기서는 왜 큐를 사용하는지, 큐를 어떤 식으로 활용하는지에 집중하며 학습하기 바랍니다. 깃허브 코드를 확인해주세요.

문제 01 요세푸스 문제 ⭐️⭐️

• 저자 권장 시간_30분
• 권장 시간 복잡도_O(N*K)
• 출제_큐
• 정답 URL_https://github.com/retrogemHK/codingtest_java/blob/main/solution/15.java

N명의 사람이 원 형태로 서 있습니다. 각 사람은 1부터 N까지 번호표를 갖고 있습니다. 그리고 임의의 숫자 K가 주어졌을 때 다음과 같이 사람을 없앱니다.

※ 이 문제는 유대인 역사가인 플라비우스 요세푸스가 만든 문제입니다.

• 1번 번호표를 가진 사람을 기준으로 K번째 사람을 없앱니다.
• 없앤 사람 다음 사람을 기준으로 하고 다시 K번째 사람을 없앱니다.

N과 K가 주어질 때 마지막에 살아있는 사람의 번호를 반환하는 solution( ) 함수를 구현해주세요.

제약 조건

• N과 K는 1이상 1000이하의 자연수입니다.

입출력의 예

01단계

N과 K에 실제 값을 넣고 요세푸스 문제를 손으로 풀어봅시다. N = 5, K = 2, 기준이 1인 경우를 예로 설명하겠습니다. N = 5이므로 이름표를 1~5로 붙이고 사람을 원형으로 배치합니다. 그리고 기준은 1입니다. 기준이 1이므로 ➊ K번째 사람은 2번 번호표를 가진 사람입니다. ➋ 이 사람을 제거하고 ➌ 다음 위치를 3으로 합니다.

02단계

같은 방식으로 ➍ 4번 번호표를 가진 사람을 제거하고 ➎ 다음 위치를 5로, ❻ 1번 번호표를 가진 사람을 제거하고 다음 위치를 3으로 합니다.

03단계

3 다음은 ➏ 다시 5이고, 이를 제거하면 3만 남습니다. ➐ 마지막은 3을 제거합니다.

문제 분석하고 풀기

문제를 다시 분석해봅시다. 사람들이 원형 테이블에 앉아 있다고 생각하고 1번부터 일정한 방향으로 한 사람씩 지목합니다. 사람이 사라진 후에도 지목 방향은 바뀌지 않습니다. 그리고 맨 마지막 사람을 지목한 다음에는 다시 처음으로 돌아갑니다. 선형 큐를 이용해 이 문제를 푸는 과정을 정리하면 다음과 같습니다. 그림은 N이 5이고 k가 3인 경우입니다.

※ 요세푸스 문제를 그림으로 나타낸 것을 보고 ‘원형 큐로 풀어야 되는 것 아닐까?’라고 생각하는 사람도 있을 것입니다. 하지만 코딩 테스트에서는 자바 컬렉션의 Queue 사용해도 메모리를 크게 낭비하지 않으므로 원형 큐를 사용하지 않아도 됩니다.

1. 첫 번째 데이터부터 마지막 데이터까지 큐에 add합니다.
2. 큐에서 k – 1번째까지의 데이터를 각각 front에서 poll하고 rear에 add합니다.
3. k번째 데이터를 poll하고 출력합니다.
4. 큐에 더는 원소가 없을 때까지 과정 2~3을 반복합니다.

과정 2가 조금 이상하게 보일 수 있지만 그림으로 보면 왜 그렇게 하는지 쉽게 이해될 겁니다.

01단계

여기서 과정 2를 봅시다. k – 1번째 원소까지 poll하고 add하면 1, 2를 각각 poll하고 add하므로 큐 상으로는 2, 1, 5, 4, 3과 같이 2가 맨 뒤에 위치하게 됩니다. 그리고 이 과정을 통해 자연스럽게 poll할 데이터는 3이 됩니다. 제거해야 할 k번째 원소가 맨 앞으로 오게 되는 것이죠.

02단계

또 다시 4, 5를 각각 poll하고 add합니다. 마지막 데이터는 5가 되며, poll할 데이터는 1이됩니다.

같은 방법으로 계속해서 poll, add를 진행합니다. 설명은 같으므로 그림만 첨부하겠습니다.

03단계

04단계

05단계

import java.util.ArrayDeque;

class Solution {
  private int solution(int N, int K) {
    // ❶ 1부터 N까지의 번호를 deque에 추가
    ArrayDeque<Integer> deque = new ArrayDeque<>();
    for (int i = 1; i <= N; i++) {
      deque.addLast(i);
    }

    // ❷ deque에 하나의 요소가 남을 때까지 반복
    while (deque.size() > 1) {
      // ❸ K번째 요소를 찾기 위해 앞에서부터 제거하고 뒤에 추가
      for (int i = 0; i < K - 1; i++) {
        deque.addLast(deque.pollFirst());
      }
      deque.pollFirst(); // ❹ K번째 요소 제거
    }

    return deque.pollFirst(); // ❺ 마지막으로 남은 요소 반환
  }
}

❶ 사람 번호에 해당하는 1~N을 큐의 초깃값으로 넣습니다. ❷ 마지막 남은 사람의 번호를 알아야 하므로 큐의 원소가 1개일 때까지 반복문을 반복합니다. ❸ K – 1번째까지는 poll한 사람의 번호를 add하는 동작을 반복합니다. 왜냐하면 우리는 K번째 사람 번호를 제거해야 하기 때문입니다. ❹ K번째 사람 번호를 제거합니다. ❺ 마지막 남은 사람의 번호를 반환합니다.

시간 복잡도 분석하기

N은 전체 사람 수 K는 제거된 사람의 번호입니다. K – 1번 poll하고 1번 add하는 동작을 N번 반복하므로 최종 시간 복잡도는 O(N * K)입니다.

※ 이 문제는 세그먼트 트리라는 자료구조를 사용하여 풀면 O(NlogN)으로 시간 복잡도를 개선할 수 있습니다만 큐를 공부하는 차원에서 요세푸스 문제를 소개한 것이므로 큐를 사용하여 풀었습니다.

자료구조, 알고리즘, 빈출 97 문제로 대비하는 코테 풀 패키지

[되기] 코딩 테스트 합격자 되기(자바 편)