[algorithm] 백준 1158번 요세푸스 문제

 

#include <iostream>
#include <list>

using namespace std;

int main() {
    int n,k;
    int cnt = 0;
    cin >> n >> k;
    list<int> l;
    list<int> res;
    for(int tmp=0; tmp<n; tmp++) l.push_back(tmp+1);

    list<int>::iterator p = l.begin();
    while(l.size() != 1)
        {
            cnt = k;
            while((cnt-1) != 0)
                {
                    p++;
                    if(p == l.end()) p = l.begin();
                    cnt--;
                }
            res.push_back(*p);
            p = l.erase(p);
            if(p == l.end()) p = l.begin();
        }
    res.push_back(*p);

    int count = 1;
    
    if (res.size() == 1)
    {
        cout << "<" << *p << ">";
    }
        
    else
    {
        cout << "<";    
        for(int tmp : res)
        {
            if(count == 1)
            {
                 cout << tmp << ",";
            }
            else if(res.size() == count) cout << " " << tmp;
            else cout << " " << tmp << ",";
            count++;
        }
        cout << ">";
    }

    return 0;
}

 

우선 1~n(n은 입력값)까지를 담은 배열을 만들고

배열의 크기가 1이 될때까지

반복자를 기준으로 k번째 원소를 제거해 나가면된다

 

만약 반복자가 end()로 갔다면 begin()으로 설정해주고

erase 할 때도 return값으로 end()가 왔다면 begin()으로 설정해야한다

 

k값을 cnt로 복사시킨 이유는

erase 이후 다시 k번째를 삭제해야하는데

k는 1씩 빼져서 1이 되어있는 상태고 초기화를 시켜야하는데

원래 k 입력값을 모르니까 cnt로 복사한 것이다

 

이 문제는 결과를 출력할 때

맨 앞과 맨 뒤에 <, >를 출력해줘야한다

이거 때문에 몇 번 오류가 났었다 -.-

코드를 간소화하는 연습을 해야할 필요가 있는 것 같다