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

백준 2164번 문제  -  카드2

2164번: 카드2

---

문제 분석

 

• 맨 위 한 장 버리고, 맨 위 한 장은 빼서 맨 뒤로 넣음
• 이때 마지막에 남는 하나의 카드 번호는?

 

---

해결 키 포인트

• Queue 개념 이해가 필요
• Queue Class가 자바에 존재

---

 

큐(Queue) 설명

 

큐의 구조는 다음과 같다. 즉 큐의 특징은 "삽입과 삭제 연산 방식: FIFO(선입선출)"이다

 

• FIFO: First-in First-out 

Do It! 알고리즘 코딩 테스트 기본

 큐는 너비 우선 탐색(BFS) 종류의 코딩 테스트에 효과적 

 

큐  용어

 

위치

• rear: 큐에 가장 끝 데이터
• front: 큐에서 가장 앞의 데이터

 

연산

• add: rear 위치에 새로운 데이터를 삽입
• poll: front 위치에 현재 있는 데이터를 삭제하고 확인하는 연산
• peek: front 위치에 현재 있는 데이터를 단순 확인

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	public static void main(String [] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		// N 입력
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		
		// 1~N까지 Queue에 삽입
		Queue<Integer> queue = new LinkedList<Integer>();
		for(int i=1;i<=N;i++) 
			queue.add(i);
		
		// Queue에 하나만 남을 때까지 반복
		while(queue.size() > 1) {
			// 맨위에 있는 수 꺼내기
			queue.poll();
			
			// 맨위에 있는 수 꺼내서 맨뒤에 삽입
			int reInsert = queue.poll();
			queue.add(reInsert);
		}
		
		// 출력
		System.out.println(queue.poll());
	}
}