백준 2164번 - 카드2 (C/C++)

 

 

 

 

시간 초과가 발생한 이유와 함께 어떻게 풀이했는지 적어보려고 한다.

 

 

 

 

 

 

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

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

자료구조 문제인데 아직 자구를 배우지를 않아서 queue 대신 vector을 사용하다가 시간 초과가 발생했다.

        // 1.
        vec.erase(vec.begin());
        
        // 2.
        vec.push_back(vec.front());
        vec.erase(vec.begin());

 

벡터 요소로 확인해봤을 때 문제에서 요구하는 핵심 형식은 다음과 같을 것이다.

 

1. N이라는 정수를 입력받는다. (이때 N은 500000만큼의 숫자가 될 수도 있다.)

 

2. 첫 번째 원소를 제거한다.

( 두 번째 원소가 맨 앞으로 오게 된다. )

 

3. 그 다음 맨 앞으로 온 원소는 맨 뒤로 보낸다.

( 즉, 맨 앞으로 온 원소를 맨 뒤로 보낸다음, 맨 앞에 있던건 삭제한다.)

 

이 과정이 계속 반복된다는 점을 이용해 코드를 구현해보아야 할 것이다. 이제 코드를 확인해보자.

 

 

 

 

---

 

 

 

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

int main() {
	int N;
	cin >> N;
	queue<int> que;

	for (int i = 0; i < N; i++) 
	{
		que.push(i+1);
	}
	while (que.size() > 1)
	{
		que.pop();
		que.push(que.front());
		que.pop();


	}
	cout << que.front() << endl;
}

 

다음과 같은 방식으로 문제를 풀이했다.

먼저 vector와 que의 차이를 알아보아야 하는데, 왜 vector에서만 시간 초과가 발생할까?

 

큐와 벡터의 차이점 정리

특징 : 큐 (Queue) vs 벡터 (Vector)

설계 목적	FIFO 구조 처리	동적 배열 및 임의 접근
시간 복잡도 (추가/제거)	O(1) (pop, push)	O(N) (erase 첫 요소)
직관성	간단하고 명확	추가적인 인덱스 관리 필요
최적화 가능성	기본적으로 최적화됨	최적화하려면 추가 로직 필요

 

찾아보니 Queue는 Vector가 시간복잡도를 O(N)으로 수행하는 동안 front, back, push, pop 같은 연산이 O(1)의 시간복잡도만으로 이루어질 수 있도록 설계된 자료구조이다.

 

예를들면 다음과 같은 erase를 생각해보자.

O(N)

vec.erase(vec.begin())

 

해당 코드는 첫 번째 요소를 제거(erase) 하고, 나머지 요소는 연쇄적으로 이동시켜야 하므로 O(N)의 시간복잡도가 발생한다. ( 반면 push_back()는 맨 뒤에 추가하는 형식이니 O(1)만을 수행하게 된다.)

 

O(1)

q.pop();

 

이때 queue의 pop와 push는 모두 O(1)의 시간복잡도만 발생시킨다.

따라서 각각의 원소 데이터를 전부 이동시키지 않고 최적화할 수 있는 코드를 작성하기 위해서는 vector에서 인덱스 형식을 조작하는 방식을 채택하거나 그냥 queue를 사용해야 한다.

 

그럼 벡터는 왜 사용하는걸까?

궁금해서 찾아봤는데 queue는 FIFO(First-In-First-Out)만을 처리하기에 적합하게 구성되어 있지만, vector는 queue와는 달리 임의 접근이라던지 STL 알고리즘 접근성이 훨씬 높다. vector을 사용하는 이유는 여러가지 기능 구현에 있어서 높은 자율성에 달려있음을 확인할 수 있었다.

 

queue를 사용해야할 때는 지금처럼 메모리를 재활용해야 하거나 '앞에서 제거'와 같은 행동을 수행해야 할 때 ,

시간복잡도를 줄일 수 있는 효과를 가져오니 앞으로도 문제를 풀 때 활용해보면 좋을 것 같다.