백준알고리즘 2164번 카드2 C#

세부 정보

• 사이트: 백준알고리즘
• 번호: 2164
• 문제명: 카드2
• 언어: C#
• 분류: 자료 구조, 큐
• 비고: 

 

문제

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

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

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

N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

 

입력

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

 

출력

첫째 줄에 남게 되는 카드의 번호를 출력한다.

 

풀이

큐는 선입선출 방식이다. 따라서 처음 접하면 어떻게 풀어야 할 지 답이 안 나올 수도 있다. 하지만 역발상으로 맨 아래에 1번 카드부터 놓는 방법으로 문제를 풀면 해결할 수 있다.

(int)를 사용해 오브젝트를 정수 형태로 언박싱해 임시 변수에 큐의 값을 담을 수 있다.

using System.Collections;
using System.Text;

// StreamReader, StreamWriter, StringBuilder 선언
StreamReader sr = new StreamReader(Console.OpenStandardInput());
StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
StringBuilder sb = new StringBuilder();

// 카드를 저장할 큐
Queue queue = new Queue();
// 카드의 개수를 입력 (1부터 n까지)
int n = Convert.ToInt32(sr.ReadLine());

// 큐에 카드를 대입한다.
// 문제와 반대로 맨 아래에 1번 카드부터 놓는다.
for (int i = 1; i <= n; i++)
    queue.Enqueue(i);

// 카드를 버린 후 맨 아래의 카드를 맨 위로 옮기기 위한 임시 변수
int temp;

// 카드가 1개만 남을 때까지 반복한다
while (queue.Count > 1)
{
    // 카드를 버린다
    queue.Dequeue();
    // 카드를 임시 변수에 정수 형태로 바꿔서 저장한다.
    temp = (int) queue.Dequeue();
    // 임시 변수에 저장된 카드를 맨 위에 올린다.
    queue.Enqueue(temp);
}

// 남게 되는 카드 번호를 스트링 빌더에 넣는다.
sb.Append(queue.Peek() + "\n");
// 남는 카드 번호를 출력한다
sw.WriteLine(sb.ToString());

sr.Close();
sw.Close();

 

후기

이 문제가 생각외로 쉽게 풀렸다. 역발상의 성공적인 예시라고도 할 수 있다. 한 달 동안 매일 한 문제씩 푼 성과가 서서히 수면 위로 올라오고 있다. 심지어 한번에 정답을 맞추는 것도 성공했다. 좀 더 어려운 문제도 이런 식으로 술술 풀리려면 더 많은 시간을 투자해야 한다.