[백준] 2164번: 카드2 C++로 풀어보기

2164번 설명

어떻게 풀까? (문제를 보고 처음 든 생각)

큐를 사용해서 풀면 될 것 같다.

먼저 큐의 front를 한 번 pop하고,

그리고 임시 변수에 갱신된 큐의 front를 저장하고,

큐의 front를 다시 pop한다.

그리고 임시 변수를 큐에 push한다.(위에 있던 수를 밑으로 옮기는 효과)

 

코드

#include <bits/stdc++.h>
using namespace std;


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	queue <int> q;

	int n;
	int temp = 0;
	cin >> n;
	

	for (int i = 1; i <= n; i++) {
		q.push(i); // 카드들을 큐에 넣는다.
	}

	while (q.size() != 1) {
		
		if (!q.empty()) {
			q.pop(); // 맨 위의 카드를 버린다.
		}

		temp = q.front(); // 제일 위의 카드 숫자를 temp에 저장
		
		if (!q.empty()) {
			q.pop(); // 맨 위의 카드를 버린다.
		}
		
		q.push(temp); // temp를 큐에 넣는다.(아까 제일 위에 있었던 카드 숫자)
	}

	cout << q.back();
}

 

결과

2164번 결과

 

메인 아이디어는 틀리지 않았다. 다만 큐가 empty인지 체크를 안하고 pop을 해서 런타임 에러가 난 적이 있기도 했고, 틀림없이 맞다고 생각했는데 왜 자꾸 시간 초과가 나는지 이해가 안 간적도 있었다.

 

밑은 '시간 초과'가 된 코드다.

#include <bits/stdc++.h>
using namespace std;


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	queue <int> q;

	int n;
	int temp = 0;
	cin >> n;
	

	for (int i = 1; i <= n; i++) {
		q.push(i); // 카드들을 큐에 넣는다.
	}

	while (true) {
		
		if (!q.empty()) {
			q.pop(); // 맨 위의 카드를 버린다.
		}

		if (q.size() == 1) { // 만약 남은 카드가 한개면
			cout << q.back(); // 남은 카드의 숫자를 출력한다.
			return 0; // 종료
		}
		temp = q.front(); // 제일 위의 카드 숫자를 temp에 저장
		if (!q.empty()) {
			q.pop(); // 맨 위의 카드를 버린다.
		}
		q.push(temp); // temp를 큐에 넣는다.(아까 제일 위에 있었던 카드 숫자)
	}
}

 

정답 처리 된 코드와 차이가 커보이지 않는다. 그렇다면 왜 이 코드만 시간 초과가 된걸까? 아직도 이유는 잘 모르겠다.

(while문의 조건의 차이가 이유라고 추측은 해본다)