[Algorithm] BOJ 1158 요세푸스 문제 (STL)

문제 링크

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

문제 풀이

요세푸스 순열을 푸는 문제이다. 요세푸스 순열이란, n 과 k가 주어졌을 때, 숫자를 1 ~ n 까지 원형으로 나열해놓고, k번째 숫자마다 지웠을 때, 지워진 순서대로 생긴 숫자의 나열이다.

원형 연결 리스트를 구현해놓고 풀면 풀이는 간단하지만, 포인트를 이용한 구현이 필요하므로 구현은 잠시 뒤로 미루고,, list STL과 iterator를 통해 해결했다.

풀이를 간단하게 설명하자면, 그냥 숫자를 나열해놓고, k번째 마다 지운게 끝이다 ! 다만, 맨 끝에 숫자에서 맨 앞으로 돌아오는 부분의 구현이 필요하기 때문에 해당 부분을 iterator를 사용해서 해결했다.

원형 연결리스트를 구현하면, 포인터 위치에 따른 조건문이 사라질 수 있어서 문제 풀이 코드가 깔끔해질 것 같다.

파이썬은 반복자가 없으므로, idx라는 변수를 통해 위치를 직접 제어해준 것을 제외하면 풀이는 같다 !

코드

C++

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <queue>
#include <list>

using namespace std;

int main() {

    ios_base::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    vector<int> answers;
    list<int> josephus;

    for (int i = 0; i < n; i++) {
        josephus.push_back(i + 1);
    }

    int count = 0;
    list<int>::iterator cur = josephus.begin();
    while (!josephus.empty()) {
        count += 1;
        if (count == k) {
            answers.push_back(*cur);
            
            // 만약 현재 위치가 마지막이라면, 지우고 cur을 리스트의 맨 앞으로 이동
            if (cur == josephus.end()) {
                josephus.erase(cur);
                cur = josephus.begin();
            } else {
            	// 맨 앞이 아니라면, 지우고 cur을 바로 다음 위치로 이동
                cur = josephus.erase(cur);
            }
         	count++;
        } else {
        	// 지우지 않았으면 cur을 다음 위치로 이동
            cur++;
        }
		
        // 이동 후 위치가 마지막일 경우, cur을 리스트의 맨 앞으로 이동
        if (cur == josephus.end()) {
            cur = josephus.begin();
        }
    }

    cout << "<";
    for (int i = 0; i < answers.size(); i++) {
        cout << answers[i];
        if (i != answers.size() - 1) {
            cout << ", ";
        }
    }
    cout << ">";

    return 0; 
}

Python

import sys

input = sys.stdin.readline

n, k = map(int, input().split())

josephus = [i for i in range(1, n + 1)]
answers = []

count, idx = 0, 0
while josephus:
    count += 1
    if count == k:
        answers.append(josephus[idx])
        if idx == len(josephus) - 1:
            del josephus[idx]
            idx = 0
        else:
            del josephus[idx]
        count = 0
    else:
        idx += 1
    
    if idx == len(josephus):
        idx = 0

answer = "<"
for i in answers:
    answer += str(i) + ", "
else:
    answer = answer[:-2]
    answer += ">"
print(answer)

Python (improved code)

import sys
from collections import deque

input = sys.stdin.readline

n, k = map(int, input().split())

circle = deque([i for i in range(1, n+1)])
seq = []

while circle:
    circle.rotate(-k)
    seq.append(circle.pop())

print('<' + ', '.join(map(str, seq)) + '>')

여담으로 파이썬의 deque와 rotate 메서드를 함께 사용하면, 하나하나 돌면서 인덱스를 제어해주지 않아도 되어서 풀이도 깔끔하고 시간복잡도가 엄청나게 개선된다.

사진에서 위 제출은 deque를 이용한 코드이고, 아래 제출한 파이썬 코드는 위치를 제어하며 요소와 위치를 매번 검사했던 코드이.