JOSEPHUS(조세푸스)

(출처) https://algospot.com/judge/problem/read/JOSEPHUS

그냥 연결리스트를 써서 풀어라

해당 문제는 연결리스트 자료구조를 이용해 문제를 풀라고 대놓고 유도하는 문제였다. 연결리스트를 사용하는 단순한 구현의 문제였고 딱히 다른 알고리즘적 사고를 필요로 하지 않았다.

연결리스트의 자료구조는 배열기반의 자료구조와 다르게 자유로운 원소의 탐색은 다소의 제한이 뒤따르지만, 중간 원소의 삽입과 삭제를 O(1) 상수시간만에 처리할 수 있으므로 해당 문제와 같이 중간중간 원소를 계속해서 삭제해 주어야 하는 경우에 사용하기 매우 적합한 자료구조이다.

(연결리스트의 경우 자료의 저장이 순차성을 띠지 않고 포인터를 기반으로 논리적인 연결을 이뤄놓았기 때문에 특정 원소 탐색을 하기 위해선 원소를 하나하나 따라가며 탐색해 나가야만 한다. 따라서 원소탐색에 O(N)의 시간복잡도가 든다. 메모리 순차저장의 특성을 지니고 있는 벡터와 같은 배열 기반의 자료구조는 O(1)에 해결할 수 있다)

연결리스트를 사용한 알고리즘의 시간복잡도를 한 번 계산해본다면 총 N-2 번의 전체 반복에다가, 한 번의 반복 당 자살한 사람의 원소 위치에서 K 번째 떨어져 있는 원소를 찾기 위해 매번 K 번의 반복이 추가로 들어가게 되므로 총 O(K * N)의 시간복잡도가 된다.

문제의 입력으로 K와 N은 최대 1,000까지 들어올 수 있으므로 해당 시간복잡도라면 충분히 해결할 수 있다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <list>

using namespace std;

int n, k;
list<int> alive;

void josephus(list<int> &alive) {
	auto iter = alive.begin();
	while (alive.size() != 2) {
		auto next_iter = alive.erase(iter);
		if (next_iter == alive.end()) {
			next_iter = alive.begin();
		}
		for (int i = 0; i < k - 1; i++) {
			next_iter++;
			if (next_iter == alive.end()) next_iter = alive.begin();
		}
		iter = next_iter;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int testcase;
	cin >> testcase;
	while (testcase--) {
		cin >> n >> k;
		alive.clear();
		for (int i = 1; i < n + 1; i++) alive.push_back(i);
		josephus(alive);
		alive.sort();

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

기억하고 싶은 점

연결리스트의 경우 iter의 연산이 단순 1회 증가(++), 단순 1회 감소(--)만 가능한다. 다음 원소에 우선적으로 1 번은 접근해야지만 그 다음 원소의 위치를 찾을 수 있으므로 vector와 같은 임의 접근 반복자의 사용은 당연히 불가능하다.

(출처)
https://eehoeskrap.tistory.com/263
https://blockdmask.tistory.com/76