[BOJ/백준] 1158 요세푸스 문제

● [문제번호 1158] 요세푸스 문제

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

1158번: 요세푸스 문제

 

● 알아야 할 것

: list 자료구조와 메소드

 

● 풀이 과정

: 주된 작업이 삭제 연산이므로 list로 구현

: 노드가 1개 남을 때 까지 재귀

: K 번째로 이동 -> 삭제 -> ( list.end()인 경우 처음으로 옮기기 ) -> 재귀

 

● 주의 할 것

: K 번째 이지만 이동 횟수는 K-1 임

: 삭제한 다음 iterator가 list.end()를 가리킬 수 있음

● 참고 할 것

: NULL

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// 삭제 작업이 많기에 list로 구현
list<int> l;
list<int>::iterator it;
int N, K;

void josephus()
{
    // 노드가 1개 남으면 출력하고 종료
    if(l.size() == 1)
    {
        cout << l.front();
        return ;
    }
    
    // k번째 이므로 k-1번 이동
    for(int k = 0; k < K - 1; k++)
    {
        // 이동 후 마지막인 경우 처음으로 옮기기
        it++;
        if(it == l.end())
            it = l.begin();
    }
    
    // 출력 후 삭제 작업
    cout << *it << ", ";
    it = l.erase(it);
    
    // 삭제 한 다음 노드가 끝인 경우 처음으로 옮기기
    if(it == l.end())
        it = l.begin();
    
    // 재귀 함수
    josephus();
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N >> K;
    
    // 리스트 초기화 작업
    for(int n = 1; n <= N; n++)
        l.push_back(n);
    
    // iterator 초기 설정
    it = l.begin();
    
    // 출력
    cout << "<";
    josephus();
    cout << ">";
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 1/2] - [200 - 자료구조 1] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	10828	스택	https://pirateturtle.tistory.com/153
2	9093	단어 뒤집기	https://pirateturtle.tistory.com/154
3	9012	괄호	https://pirateturtle.tistory.com/155
4	1874	스택 수열	https://pirateturtle.tistory.com/156
5	1406	에디터	https://pirateturtle.tistory.com/158
6	10845	큐	https://pirateturtle.tistory.com/161
7	1158	요세푸스 문제	https://pirateturtle.tistory.com/162
8	10866	덱	https://pirateturtle.tistory.com/164