[큐] 카드게임

목차

1. 풀이

(1) 문제

백준 2164번, 카드2 : https://www.acmicpc.net/problem/2164

 

핵심키워드

1. N장의 카드가 있고, 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있다.
2. 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순선대로 카드가 놓여 있다.
3. 카드가 한장 남을 때까지 제일 위에 있는 카드를 버리고, 그 다음 제일 위의 카드를 제일 아래로 옮긴다.
4. 정수의 범위는 N(1 ≤ N ≤ 500,000) 
5. 첫째 줄에 남게 되는 카드의 번호를 출력

(2) 풀이

큐 자료구조를 활용하면 쉽게 풀 수 있다.

 

큐(Queue)

- 큐는 먼저 들어온 데이터가 먼저 삭제되는 자료구조로 선입선출(FIFO : First In First Out) 리스트라고도 한다.

- 큐는 한쪽 끝에서는 데이터의 삽입만 수행되고 다른 한쪽 끝에서는 데이터의 삭제만 수행되는 리스트이다.

- 일반적으로 데이터가 삭제되는 끝을 앞(front, head), 삽입되는 다른 한쪽의 끝을 뒤(rear, tail)라고 한다.

- 큐에 데이터를 삽입할 때는 Enqueue, 삭제할 때는 Dequeue라고 한다.

- Queue라는 단어는 표 같은 것을 구매하기 위해 줄서는 모습을 의미한다.

이미지 출처 : https://www.programiz.com/dsa/queue

 

2. 정답

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        Deque<Integer> que = new ArrayDeque<>();
        for (int i = 1; i <= N; i++) {
            que.offer(i);
        }

        while (que.size() > 1) { // 카드 한장 남을 떄까지 반복
            que.poll();
            que.offer(que.poll());
        }
        System.out.println(que.peek());
        sc.close();
    }
}

- Queue<Integer> queue = new LinkedList<>() 로 받아 처리해도 되지만 성능면에서 더 좋은 ArrayDeque를 사용했다.

- 자바에선 que에 데이터를 삽입할 때 add(), offer() 메서드를 사용하고, 삭제할 때는 remove(), poll() 메서드를 사용한다.

- peek() 메서드는 큐에서 가장 앞에 있는 데이터를 삭제하지 않고 값을 반환한다.

3. 참고

- Do it 알고리즘 코딩 테스트 자바 편(김종관)