백준 1158 - 요세푸스 문제

정답 1 (1976ms)

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void print(vector<int> answer) {
    cout << "<";
    for (int i = 0; i < answer.size(); i++) {
        if (i == answer.size() - 1) {
            cout << answer[i] << ">" << endl;    
            return;
        }
        cout << answer[i] << ", ";
    }   
}

void solution(int nums, int target) {
    /*
        1. i: 계속 증가하면서 배열을 순회, turn은 제거된 사람이 아닐 때만 증가
        2. turn이 target이 되면 현재 i가 가리키는 사람 제거
        3. 현재 i가 가리키는 사람이 이미 제거된 경우 처리를 위해 i를 제거된 사람이 아닐 때까지 증가
    */
   
    vector<bool> isDeads(nums, false);
    vector<int> answer;

    int i = 0;
    while (answer.size() != nums) {
        int turn = 1;
        
        while (turn != target) {
            if (!isDeads[i]) {
                turn++;
            }

            i = (i + 1) % nums;
        }

        while(isDeads[i]) {
            i = (i + 1) % nums;
        }

        isDeads[i] = true;
        answer.push_back(i + 1);
        i = (i + 1) % nums;
    }

    print(answer);
}

int main() {
    int nums, target;
    cin >> nums >> target;

    solution(nums, target);
    
    return 0;
}

🤔 개선점

• i = (i + 1) % nums 코드 중복
• list에 1 ~ N 번호를 담고 iterater를 사용해서 begin, end, erase를 사용하는 게 더 직관적임
• 예전에 그렇게 풀었던데 왜 사고력이 퇴화됐지,,,

정답 2 (80ms)

• 6달 전에 푼 거 (해답 보고 푼 듯?)

#include <iostream>
#include <sstream>
#include <iterator>
#include <algorithm>
#include <vector>
#include <list>

using namespace std;

int main() {
    int N, K;
    cin >> N >> K;

    list<int> people;
    for (int i = 1; i <= N; i++) {
        people.push_back(i);
    }
    
    auto it = people.begin();
    cout << "<";
    
    while(!people.empty()) {
        // K - 1번 이동 (K번째 원소를 삭제하기 위해)
        for (int i = 1; i < K; i++) {
            it++;
            if (it == people.end()) { // 끝에 도달하면 처음으로 이동
                it = people.begin();
            }
        }
        
        cout << *it;
        // 현재 위치의 원소 제거
        it = people.erase(it); // erase()는 삭제 후 다음 원소를 가리킴
        
        if (!people.empty()) {
            cout << ", ";
        }
        
        if (it == people.end()) { // 삭제 후 end()이면 다시 처음으로
            it = people.begin();
        }
    }
    cout << ">";
    
    return 0;
}