백준 링크 : https://www.acmicpc.net/problem/2164

문제 개요

N장의 카드가 정수 입력으로 들어오며, 카드가 한장 남을 때 까지 맨 위의 카드를 버리고, 그 다음 위의 카드는 맨 아래로 옮기는 로직을 반복하는 문제이다.

이 로직 끝에는 마지막 1장이 남게되는데 마지막 1장의 카드 숫자를 출력하는 문제이다.

아이디어

• 큐(Queue)자료구조를 활용해서 문제를 해결한다.
  • 맨 위의 카드를 버리는 것은 pop을 통해 해결한다.
  • 맨 위의 카드를 맨 아래로 내리는 것은 push(front) 이후 pop을 통해 해결한다.

코드

// 아래의 코드는 dev c++환경에서 동작됩니다.
// visual studio에서는 bit/stdc++.h가 기본적으로 없기 때문에
// 정삭적인 작동이 되지 않을 수 있습니다.
#include <bits/stdc++.h>
using namespace std;

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

후기

처음에는 연결리스트 자료구조를 통해 이러한 로직을 구현했었는데, 정답을 맞고나서 다른 사람들이 어떻게 구현했는지 살펴보는 중 큐 자료구조를 활용한 것을 보게 되었다.

자료구조의 차이만 있을뿐 로직은 거의 동일했는데, 시간은 10배정도의 속도 차이가 존재했다. 조사끝에 큐 자료구조는 배열 기반이라 캐시 히트율이 높았고, 반대로 리스트는 노드 기반이라 캐시 히트율이 낮은 결과라는 것을 깨닫게 되었는데, CS지식으로만 듣던 것을 이렇게 직접 체감해보니 꽤나 신선했던 경험이었다.

그리고 앞으로 앞에 있는 것을 꺼내 뒤로 담는 유형의 문제가 나온다면 고민없이 큐 자료구조부터 사용해야겠다.