백준(BOJ) 1158번 조세푸스 문제

문제:  https://www.acmicpc.net/problem/1158

나의풀이 :

중간과정에서의 삽입과 삭제가 쉬운 연결리스트를 이용하였다. 복잡도는 O(N * K)

입력

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

출력

예제와 같이 조세퍼스 순열을 출력한다.

코드 ( C ++ )

#include <iostream>

#include <list>

#include <vector>

using namespace std;

int N, K;

int main()

{

cin >> N >> K;

list<int> people;

vector<int> result;

for (int i = 1; i <= N; ++i)

people.push_back(i);

list<int>::iterator kill = people.begin();

int n = N;

while (n > 0) {

for (int i = 0; i < K - 1; ++i) { // 자기포함 K번만큼 돌면서 죽일 kill 포인터를 지정해준다.

if (kill == people.end()) kill = people.begin(); // 리스트를 벗어났다면 다시 처음으로 가준다.

kill++;

if (kill == people.end()) kill = people.begin(); // 리스트를 벗어났다면 처음으로 가준다.

}

result.push_back(*kill);  // 죽이기전 result 배열에 저장한다.

kill = people.erase(kill); 

n--; 

}

cout << "<";

for (int i = 0; i < result.size() - 1; ++i)

cout << result[i] << ", ";

cout << result[result.size() - 1];

cout << ">";

return 0;

}