백준 11866 _ 요세푸스 문제 0

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

11866번: 요세푸스 문제 0

---

⭐ 내 소스 코드

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

 int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n, k;
	cin >> n >> k;
	int temp = k-1;
	vector<int> vec;
	vector<int> tem;
	for (int i = 1; i <= n; i++) {
		vec.push_back(i);
	}
	cout << "<" << vec[temp];
	
	tem.push_back(temp);
	
	while (tem.size() != n) {
		int i = 0;
		while (i < k) {
			temp++;
			if (temp >= n) {
				temp = temp - n;
			}

			if (tem.end() == find(tem.begin(), tem.end(), temp)) {
				i++;
			}
		}
		cout << ", " << vec[temp];
		tem.push_back(temp);
		
	}
	cout << ">";



	return 0;
}

 

🙏 문제 풀이

• tem.end() == find(tem.begin(), tem.end(), temp) - vector tem 에 temp 값이 없는지 확인한다
• 없으면 순열을 진행시키기 위해 i 값을 증가
• i 값이 K번 증가되었으면 출력해야되는 값이기 때문에 해당 값(vec[temp])을 출력하고 tem에 temp값을 추가하여 해당 값이 출력되어 제외된 값임을 표시

시간이 304ms가 나온 걸 보니 그다지 효율적이지 못한 코드인 것 같다. 요세푸스 순열 공부를 해서 더 효율적인 코드로 다시 풀어야겠다!

 

✨ 문제 풀이 결과