[백준]2164번 카드2(JAVA)

0. 문제 링크

https://www.acmicpc.net/problem/2164

2164번: 카드2

 

1. 문제 설명

1) 1번, ..., N번인 순서대로 카드가 놓여 있음

2) 제일 위에 있는 카드는 바닥에 버리고, 다음으로 위에 있는 카드를 제일 아래로 옮기는 과정을 반복

3) 제일 마지막에 남게 되는 카드 구하기

 

2. 입출력

// input
6

// output
4

 

3. 코드

import java.util.*;

public class b2164 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(); // N장의 카드
		Queue<Integer> q = new ArrayDeque<Integer>(); // 큐 생성
		
		for(int i = 1; i <= N; i++) { // N만큼 카드 쌓기
			q.offer(i);
		}
		
		int temp = 0;
		while(true) {
			if(q.size() == 1) {
				break;
			}
			
			q.poll(); // 카드 버리기
			
			if(q.size() == 1) {
				break;
			}
			
			temp = q.peek(); // 카드 꺼내기
			q.poll(); // 카드 버리기
			q.offer(temp); // 카드 밑으로 옮기기
		}
		
		System.out.println(q.peek()); // 제일 위에 있는 카드		
	}

}

 

실행 결과

 

4. 회고

1) FIFO 구조가 필요하므로 queue 사용

2) queue의 크기가 1일 때까지 반복하는 while 문으로 구현

 

5. Github

https://github.com/iihye/Algorithm/blob/main/Baekjoon/b2164.java