[Beakjoon] 2161번 카드1

📣
Beakjoon에서 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

제출 결과