📣
Baekjoon에서 PASS된 코드만 업데이트합니다.
알고리즘을 먼저 풀이하는 언어(Java)가 정해져있어,
풀이 언어(Python, C++, Java)가 모두 업데이트될 때까지는 시간이 걸릴 수 있습니다.

문제 제시

---

문제

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)이 주어진다.

출력

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

문제 풀이

---

해당 문제를 읽으면서 어떠한 자료구조를 써야할지 고민하는게 제일 중요하겠습니다.

우선, 가장 쉽게 접근할 수 있는 배열로 생각하자면,
옮기는 index 관리를 하고, 버려진 카드의 자리의 뒷자리를 앞으로 당겨줘야하는 작업이 필요합니다.
버린 카드를 저장하는 내용도 필요하지만, 이미 값을 빼고 마지막에 넣는 과정에서 복잡하죠.

다음은 큐입니다.
큐의 가장 큰 특징은 FIFO(Frist In Frist Out)으로 처음 넣은 데이터가 처음 나옵니다.
길이나 크기가 정해져있는게 아니라 값을 빼고 다시 넣는 과정은 편리하겠죠.

우리의 자료구조는 "큐(Queue)"입니다!
그 이후 생각해야하는 게, 버리는 카드를 생각해봅시다.
입력된 N까지의 값까지 출력되기에 정적인 배열(Array)이나 큐(Queue)도 괜찮을 껍니다.
그런데 정말 꼭 따로 저장해줘야할까요?

그쵸 굳이 필요없습니다.
원하는 상황이 왔을 때 바로 출력할 수 있도록 해주시면 되겠습니다

정리
1) 자료구조 : 큐(Queue)
2) 출력결과 : 별도 저장하지 않고, 출력하기

문제 코드

---

Java

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder("");
		Queue<Integer> card = new LinkedList<Integer>();

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

		for (int i = 1; i <= N; i++)
			card.offer(i);

		while (card.size() > 1) {
			sb.append(card.poll()).append(" "); // 하나를 꺼내서 버린다.			
			card.offer(card.poll()); // 하나를 꺼내서 맨뒤로 넣는다.
		}
		
		sb.append(card.poll());
		System.out.println(sb.toString());
	}
}

제출 결과

---