알고리즘 분류
- 구현
- 자료 구조
- 큐
문제
N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며,
1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.
이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다.
우선, 제일 위에 있는 카드를 바닥에 버린다.
그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.
예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다.
1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다.
3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다.
마지막으로 2를 버리고 나면, 버린 카드들은 순서대로 1 3 2가 되고, 남는 카드는 4가 된다.
N이 주어졌을 때, 버린 카드들을 순서대로 출력하고,
마지막에 남게 되는 카드를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 정수 N(1 ≤ N ≤ 1,000)이 주어진다.
출력
첫째 줄에 버리는 카드들을 순서대로 출력한다. 제일 마지막에는 남게 되는 카드의 번호를 출력한다.
풀이
- Queue 클래스를 이용해서 풀이해야 하는 문제
- 먼저 들어간 자료가 먼저 나오는 FIFO(First In First Out) 방식
- 큐의 한 쪽은 Front로 자료가 빠져나가는 Dequeue 연산 수행
- 큐의 한 쪽은 Rear로 자료가 들어가는 Enqueue 연산 수행
- Queue 클래스 객체 생성 [Java]
Queue<Integer> queue = new LinkedList<>();
- Queue 클래스 객체 함수 [Java]
- add, remove, element 메서드는 연산에 문제 생긴 경우 예외가 발생
- offer, poll, peek 메서드는 연산에 문제 생긴 경우 false 또는 null 반환
// Enqueue 연산 메서드
queue.add(i + 1);
queue.offer(i + 1);
// Dequeue 연산 메서드
queue.remove();
queue.poll();
// Peek 연산 메서드 (맨 처음 저장된 객체 반환)
queue.element();
queue.peek();
소스 코드
Java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class Baek2161 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int caseNum = Integer.parseInt(br.readLine());
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < caseNum; i++) {
queue.add(i + 1);
}
// queue 개수가 하나가 남을 때까지 반복
while (queue.size() != 1) {
// 맨 처음에 온 숫자 출력 후 Dequeue 연산
System.out.print(queue.poll().toString() + " ");
// Dequeue 연산 수행 한 숫자를 queue로 Enqueue 연산
queue.add(queue.poll());
}
System.out.print(queue.poll());
}
}
Python
case = int(input())
queue = []
for i in range(case):
queue.append(i)
while (len(queue) != 1): # queue 개수가 하나가 남을 때까지 반복
print(queue.pop(0)+1, end=' ') # 맨 처음에 온 숫자 출력 후 Dequeue 연산
queue.append(queue.pop(0)) # Dequeue 연산 수행 한 숫자를 queue로 Enqueue 연산
print(queue.pop()+1)
Ghost