JArchive 프로그래밍 일기

문제

요세푸스 문제 백준 1158

list 를 이용한 코드

#include <bits/stdc++.h>
using namespace std;
​
int N; // 초기 인원
int K; // 제거할 차례
list<int> L;
list<int> ::iterator cur;
​
void input(){
​
    cin >> N >> K;
​
    for(int i = 1; i <= N; i++){
        L.push_back(i);
    }
​
    cur = L.begin(); // 위치 참조자
​
    cout << '<';
​
    while(L.size() > 1){
​
        // K만큼 이동
        for(int i = 0; i < K-1; i++){
            cur++;
            if(cur == L.end()){
                cur = L.begin();
            }
        }
​
        cout << *cur << ", ";
​
        cur = L.erase(cur);
        if(cur == L.end()){
            cur = L.begin();
        }
    }
​
    cout << *cur << '>';
​
}
​
int main(void) {
​
    ios_base::sync_with_stdio(0);
    cin.ignore(0);
​
    input();
    return 0;
​
}

queue를 이용한 코드

#include <bits/stdc++.h>
using namespace std;
​
int N; // 사람 수
int K; // 제거 순서
queue<int> q;
vector<int> answer; // 제거순서의 사람을 저장한다. 
​
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.ignore(0);
​
    cin >> N >> K;
​
    for(int i = 1; i <= N; i++){
        q.push(i);
    }
​
    while(!q.empty()){
​
        int cnt = K-1;
​
        while(cnt--){
            q.push(q.front());
            q.pop();
        }
        answer.push_back(q.front()); // 제거한 숫자를 저장함 
        q.pop();
    }
​
    cout << '<';
    for(int i = 0; i < answer.size()-1; i++){ // 포맷에 맞춰 답 출력 
        cout << answer[i] << ", ";
    }
    cout << answer[answer.size()-1] << '>';
    return 0;
}

리뷰

queue를 이용해 푸는 것이 좀 더 직관적인 것 같다.

3번째 사람을 제거하려면, 2번 push, pop 한 후에, 정답 배열에 사람 숫자를 저장하고 pop 만 한다.