2164번 : 카드 2

문제는 다음과 같습니다.

https://www.acmicpc.net/problem/2164

2164번: 카드2

 

풀이 코드는 다음과 같습니다.

#include <iostream>
#include <queue>
using namespace std;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  queue<int>q;
  int n;
  cin>>n;
  for(int i{0};i<n;i++)
    {
      q.push(i+1);
    }
  while(q.size()!=1)
    {
      q.pop();
      int temp = q.front();
      q.pop();
      q.push(temp);
    }
  cout<<q.front()<<"\n";
  
  return 0;
}

문제에서 요구하는 "두 번째로 위에 있는 원소를 맨 뒤로 보내기"는 큐를 통해 쉽게 해결할 수 있으므로 큐를 이용하여 풀었습니다.

첫 번째로 맨 위에 있는 원소는 버리기 때문에 pop 함수를 이용해서 버리고 이후 두 번째로 맨 위에 있는 원소는 기억해두었다가 기존의 것을 빼고 기억해둔 값을 넣는 과정으로 해결했습니다.

이후 하나만 남으면( 큐의 크기가 1이면 ) 남은 하나의 원소를 출력함으로써 문제를 해결할 수 있습니다.