[Algorithm/Kotlin] 백준 2164번 카드2: Queue를 활용한 풀이법

 

문제 설명

 

N장의 카드가 있습니다. 카드는 1부터 N까지 번호가 붙어 있고, 1번 카드가 제일 위, N번 카드가 제일 아래에 놓여 있습니다. 이 상태에서 다음 동작을 반복하여 카드가 한 장만 남을 때까지 진행합니다:

1. 제일 위에 있는 카드를 버린다.
2. 그 다음, 제일 위에 있는 카드를 제일 아래로 옮긴다.

마지막에 남는 카드를 구하는 프로그램을 작성합니다.

---

문제 해결 아이디어

이 문제는 큐(Queue) 자료구조를 사용하면 직관적으로 해결할 수 있습니다. 문제에서 요구하는 동작이 큐의 FIFO(First In First Out) 구조와 일치하기 때문입니다.

1. 큐 초기화:
   •    1부터 N까지의 숫자를 큐에 삽입합니다.
        예: N=6이면 [1,2,3,4,5,6].
2. 홀수와 짝수 턴 처리:
   •    홀수번째 턴:
     •    poll() 메서드를 사용해 큐의 맨 앞 요소를 제거합니다.
   •    짝수번째 턴:
     •    poll() 메서드로 큐의 맨 앞 요소를 제거한 뒤, 제거된 요소를 큐의 맨 뒤에 추가합니다.
3. 결과 출력:
   •    큐의 크기가 1이 되면 마지막으로 남은 카드를 출력합니다.

---

구현 코드

import java.util.LinkedList
import java.util.Queue

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val n = br.readLine().toInt()

    val queue: Queue<Int> = LinkedList() // 1부터 N까지의 숫자를 담는 큐

    // 1. 큐 초기화
    for (i in 1..n) {
        queue.add(i)
    }

    var turn = 1 // 반복 횟수를 추적하는 변수

    // 2. 큐 동작 반복
    while (queue.size > 1) {
        if (turn % 2 == 1) { // 홀수번째 턴: 카드 제거
            queue.poll()
        } else { // 짝수번째 턴: 카드 제거 후 맨 뒤로 이동
            val even = queue.poll()
            queue.add(even)
        }
        turn++ // 턴 증가
    }

    // 3. 마지막 남은 카드 출력
    bw.write("${queue.peek()}")
    bw.flush()
    bw.close()
}

 

---

시간 복잡도 분석

1. 큐 초기화

• 큐에 N개의 숫자를 삽입하는 데 걸리는 시간은 O(N)입니다.

2. 반복문

• 큐의 크기가 N에서 1까지 줄어들며, 각 반복에서 두 가지 동작을 수행합니다:
  1. poll() 메서드 (제거): O(1)
  2. add() 메서드 (추가, 짝수 턴에만): O(1)
• 최악의 경우 반복문은 N−1번 실행되므로, 전체 시간복잡도는 O(N)입니다.

최종 시간복잡도

• 큐 초기화 O(N) + 반복문 O(N) = O(N)

---

사용한 자료구조

큐 (Queue)

• 이 문제는 FIFO(First In First Out) 구조가 필요하며, Java의 LinkedList를 사용하여 큐를 구현했습니다.
• 주요 메서드:
  1. poll(): 큐의 맨 앞 요소를 제거하고 반환합니다.
  2. add(): 큐의 맨 뒤에 요소를 추가합니다.
  3. peek(): 큐의 맨 앞 요소를 확인합니다.

---

예제 실행 결과

입력 N출력

4	4
6	4
7	6
10	4

---

큐의 동작 예제 N=6

초기 상태: [1,2,3,4,5,6]

1. 1번 턴 (홀수):
   •    1 제거 → [2,3,4,5,6]
2. 2번 턴 (짝수):
   •    2 제거, 뒤로 이동 → [3,4,5,6,2]
3. 3번 턴 (홀수):
   •    3 제거 → [4,5,6,2]
4. 4번 턴 (짝수):
   •    4 제거, 뒤로 이동 → [5,6,2,4]
5. 5번 턴 (홀수):
   •    5 제거 → [6,2,4]
6. 6번 턴 (짝수):
   •    6 제거, 뒤로 이동 → [2,4,6]

최종 남은 카드: 4

 

---

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