백준 2164: 카드 2(java)

문제

---

풀이

 

큐의 front에서 뽑아낸 값을 rear에 삽입해야 하므로, 양 끝단에서 삽입과 삭제가 모두 일어나는 덱을 사용하여 풀면 된다.

(덱에 대한 자세한 설명은 링크)

https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/Deque.html

Deque (Java SE 21 & JDK 21)

문제를 읽어 보면, 

• 제일 위에 있는 카드를 바닥에 버리는 것 = removeFirst()
• 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮기는 것  = removeFirst()해서 addLast()

으로 생각할 수 있다.

 

우선 N을 입력받고, for문을 사용해 덱에 정수 값들을 삽입해 준다.

for(int i=1; i<N+1; i++) {
	deque.addLast(i);
}

1부터 출력되어야 하므로 addFirst()가 아닌 addLast()를 사용한다. getFirst(), removeFirst()로 값을 뽑아내는 상황에서 addFirst()를 하면 N부터 출력되기 때문이다. getLast, removeLast()로 출력할 경우 addFirst()로 삽입한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
		Deque<Integer> deque=new LinkedList<>();
		
		int N=Integer.parseInt(in.readLine());
		for(int i=1; i<N+1; i++) {
			deque.addLast(i);
		}
		
		while(true) {
			if(deque.size()==1) {
				System.out.println(deque.getFirst());
				break;
			}
			deque.removeFirst();
			deque.addLast(deque.removeFirst());
		}
	}
}

덱을 직접 구현하지 않고 라이브러리에 기본 제공되는 덱 인터페이스를 사용하였다.