선형 자료구조 - 조세푸스 문제

 

선형 자료구조 - 조세푸스 문제

 

 

문제 출저 - 알고스팟 https://algospot.com/judge/problem/read/JOSEPHUS

 

 

 

 

 

풀이생각

1. 하나의 리스트에서 2명이 남을 때까지 자살한 병사를 삭제

 => 특정 위치의 삭제가 용이한 연결리스트를 사용하자

 => remove를 사용하려 했으나, 이것은 원소를 탐색하여 제거하는 것. 연결리스트를 선택한 이유가 없어짐

 => iterator를 지우는 erase를 사용하자

 

2. 마지막 원소에서 어떻게 iterator를 처음으로 옮겨줄까?

 => Linked list 마지막 원소의 다음 iterator에 접근했을 때, Linked list의 begin으로 iterator를 옮겨주기

 => 마지막 원소의 다음 주소를 가리키는 end를 사용하자

 

3. 그럼 어떤 방식으로 iterator를 옮겨갈까?

 => 마지막 원소에서 넘어가는 것을 검사해야하기 때문에, +K가 아닌 ++로 하나씩 접근하자

 => iterator가 end에 도달하면 begin으로 옮겨주기

 

 

 

 

#include <iostream>
#include <list>
 
using namespace std;
 
int N, K; // 3<= N,K <=1000
 
list<int> func(void) {
    list<int> armies;
    list<int>::iterator idx;
 
    for (int i = 1; i <= N; ++i) {
        armies.push_back(i);
    }
 
    idx = armies.begin();
 
    for (int i = 0; i < N-2; ++i) {
        idx = armies.erase(idx);
        if (idx == armies.end()) {
            idx = armies.begin();
        }
        for (int j = 0; j < K-1; ++j) {
            ++idx;
            if (idx == armies.end()) {
                idx = armies.begin();
            }
        }
    }
    return armies;
}
 
int main() {
    cin.sync_with_stdio(false);
 
    int T; // T <= 50
    cin >> T;
 
    while (T--) {
        cin >> N;
        cin >> K;
 
        list<int> res = func();
 
        cout << res.front() << " " << res.back() << "\n";
    }
}