Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

19. 큐, 덱

큐와 덱을 구현하고 사용해 봅시다.

Java / Python

2. 카드2

2164번

큐를 사용하여 동작을 구현하는 문제

이번 문제는 N장의 카드가 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 문제입니다. 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮기는 것을 반복해 마지막에 남는 카드를 구하는 원리입니다.

• Java

import java.util.Queue;
import java.util.LinkedList;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
public class Main {
 
	public static void main(String[] args) throws IOException {
	
		Queue<Integer> queue = new LinkedList<>();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));	
		
		int N = Integer.parseInt(br.readLine());
		
		for(int i = 1; i <= N; i++) {
			queue.offer(i);
		}		
		
		while(queue.size() > 1) {
			queue.poll();	// 맨 앞 원소 버리기
			queue.offer(queue.poll());	// 맨 앞 원소 버리고 한번 더 버리면서 버려진 원소를 맨 뒤에 삽입 
		}
		
		System.out.println(queue.poll());	// 마지막으로 남은 원소 출력 
	}
}

• Python

import sys 
from collections import deque 

N = int(sys.stdin.readline()) 
queue = deque() 

for i in range(N): 
    queue.append(i + 1) 
    
while len(queue) > 1: 
    queue.popleft() 
    queue.append(queue.popleft()) 
    
print(queue.pop())