2164번 카드2

문제링크 : www.acmicpc.net/problem/2164

2164번: 카드2

 

---

---

<알고리즘>

  1) 1~N번 카드를 queue에 넣어준다(push)

  2) queue의 size가 1보다 클때까지 반복

     2-1) 맨 위 카드 빼기(pop)

     2-2) queue의 사이즈 확인하고 종료할지 정하기

     2-3) 맨 위 카드 맨뒤에 넣어주고 맨 앞에 카드 빼기(push , pop)

  3) 하나 남은 queue의 카드 출력

 

 

 

버전 1. STL <vector> 사용 (시간초과)

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

int main() {
	int N = 0;
	cin >> N;

	vector <int> v;
	for (int i = 1; i <= N; i++) {
		v.push_back(i);
	}

	while (v.size() > 1) {
		v.erase(v.begin());
		if (v.size() == 1) { break; }
		else {
			v.push_back(v[0]);
			v.erase(v.begin());
		}
	}
	
	cout << v.front() << "\n";
	return 0;
}

 

 

버전 2.  STL <queue> 사용 ( 메모리 : KB     시간 : ms )

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

int main() {
	int N = 0;
	cin >> N;
	
	queue<int>q;
	for (int i = 1; i <= N; i++) {
		q.push(i);
	}

	while (q.size() > 1) {
		q.pop();
		if (q.size() == 1) { break; }
		else {
			q.push(q.front());
			q.pop();
		}
	}

	cout << q.front() << "\n";
	return 0;
}