[백준] 단계별로 풀어보기(단계:19,큐/덱,JAVA)2164번, 카드 2

문제 링크

2164번: 카드2

 

www.acmicpc.net

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

기본적으로 큐는 FIFO(선입선출)의 자료구조를 가지고 있습니다.

FIFO는 먼저 들어간 데이터들이 출력할 때 먼저 나온다는 이야기입니다.

예를 들어 3, 2, 1을 순서대로 큐에 저장한 뒤 하나씩 꺼내보겠습니다.

1. 3을 큐에 넣었을 때

3

2. 2을 큐에 넣었을 때

3

2

3. 1을 큐에 넣었을 때

3

2

1

4. 큐에 하나의 자료를 출력하라는 명령이 떨어졌을 때

3

2

1

5. 다시 자료를 출력하라는 명령이 떨어졌을 때

2

1

위에 표를 보면 가장 먼저 저장된 데이터가 먼저 출력되는 것을 볼 수 있듯이 큐는 FIFO형태의 자료구조입니다.

Java에서 큐를 표현하려면 LinkList<>()로 선언해주어야 하므로 큐를 선언해주었습니다.

문제에 내용을 살펴보면 간단한 알고리즘이 발견됩니다.

1. 큐로 보았을 때 처음 저장된 데이터와 다음 데이터를 꺼냅니다.

2. 2번째로 꺼낸 데이터를 큐에 저장합니다.

3. 큐의 사이즈가 1이 될 때까지 반복합니다.

예제 입력1로 살펴보자면

123456 -> 34562

34562 -> 5624

5624 -> 246

246 -> 64

64 -> 4   -> 반복 종료

결과 = 4

• BufferedReader를 사용하여 입력 값을 받았습니다.
• 반복문을 통해서 큐에 번호를 초기화하였습니다.
• 반복문을 통해 큐에 내용을 poll()하고 offer를 반복하여 큐의 값이 1개 남을 때까지 반복하였습니다.
• 하나 남은 결과을 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과를 출력하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static Queue<Integer> queue = new LinkedList<>();	//번호 저장하는 큐
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//입력 값을 받는 BufferedReader
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		//결과 값을 출력하는 BufferedWriter
		int num = Integer.parseInt(br.readLine());	//입력 값 저장
		for(int i=1;i<=num;i++)		//큐 초기화
			queue.offer(i);	
        	//-------카드 연산----------
		while(true) {
			if(queue.size()==1)
				break;
			queue.poll();
			int temp = queue.poll();
			queue.offer(temp);
		}
		bw.write(queue.poll() + "\n");	//결과 BufferedWriter에 저장
		bw.flush();		//결과 출력
		bw.close();
		br.close();
	}
}