[백준] 2164번 : 카드2

문제

1부터 n까지의 숫자가 적힌 카드가 순서대로

가장 위에는 1로 시작해서 맨 밑에 n인 카드가 있을 때

아래와 같은 동작을 반복한다.

 

가장 위에 있는 카드를 뺀 후에 가장 위에 있는 카드를

카드의 가장 밑에 깔아 둔다.

 

이 과정을 반복하여 가장 마지막에 남는 카드를 구하라

 

접근 방식

가장 먼저 들어오는 1이 가장 먼저 나가는 구조니 큐를 사용하면 적당해 보인다.

 

가장 위에 카드를 빼고 하나를 더 빼야 하니

큐에서 두 개를 뺀 후 두 번째로 뺀 값을 다시 큐에 넣어준다.

 

이 과정을 큐의 크기가 1이 될 때까지 반복한다.

 

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(br.readLine());

		Queue<Integer> queue = new LinkedList<>();

		for (int i = 1; i <= n; i++) {
			queue.offer(i);
		}


		while (queue.size() != 1) {
			queue.poll();
			queue.offer(queue.poll());
		}

		bw.write(queue.poll() + "");
		bw.flush();
	}
}