[백준] S5 2161번 카드1 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

2161번: 카드1

[문제] 

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.

이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 버린 카드들은 순서대로 1 3 2가 되고, 남는 카드는 4가 된다.

N이 주어졌을 때, 버린 카드들을 순서대로 출력하고, 마지막에 남게 되는 카드를 출력하는 프로그램을 작성하시오.

[입력]

첫째 줄에 정수 N(1 ≤ N ≤ 1,000)이 주어진다.

[출력]

첫째 줄에 버리는 카드들을 순서대로 출력한다. 제일 마지막에는 남게 되는 카드의 번호를 출력한다.

 

---

[풀이]

1. n을 입력받아준다.

2. 1부터 n까지의 숫자를 큐에 담아준다.

3. 큐가 빌 때까지 큐의 맨 위를 빼서 StringBuilder에 담아주고, 큐의 값을 빼서 큐에 담아주는 것을 반복한다.

4. 마지막의 결과를 출력한다.

[접근]

1. 처음에는 규칙을 찾아서 풀면 되겠다고 생각하였다.

2. 하지만 굳이 규칙을 찾지 않고 queue에 담아서 결과를 처리하면 되겠다고 생각하고 해당 방법으로 문제를 풀었다.

[코드]

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Queue<Integer> q = new LinkedList<Integer>();
		
		int n = Integer.parseInt(br.readLine());
		
		// n까지의 카드를 큐에 담아주기
		for (int i = 1; i <= n; i++) {
			q.offer(i);
		}
		
		StringBuilder sb = new StringBuilder();
		
		// 큐가 빌 때까지 반복
		while (!q.isEmpty()) {
			// 큐의 가장 앞을 빼주고 StringBuilder에 담아주기
			sb.append(q.poll()).append(" ");
			
			// 큐가 비었다면 탈출
			if (q.isEmpty())
				break;
			
			// 큐의 가장앞을 빼서 마지막에 담아주기
			q.offer(q.poll());
		}
		
		// 결과를 출력
		System.out.println(sb.toString());
	}
}