[백준/C++/Queue] 1158 - 요세푸스 문제

1. 문제 링크

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

1158번: 요세푸스 문제

 

2. 문제 해석

• input: n, k
• output: n개의 element가 있는 요세푸스 순열
• 원으로 둘러앉아 하나씩 제거
• 예제 입력 1: 7 3 입력
  
  • i = 0 -> 3 push
  • i = 1 -> 3 + 3 = 6 push
  • i = 2 -> 6 + 3 - 7 = 2 push
  • i = 3 -> 2 + 3 = 5 push
  • i = 4 -> 5 + 3 - 7 = 1 push
  • i = 5 -> 1 + 3 = 4 push
  • i = 6 -> 4 + 3 = 7 push

3. 발생한 문제 및 문제 해결

•  첫 번째 시도:
  • queue STL 사용
  • 순열 순서대로 push 하고 print할 때 하나씩 pop
  • 이전에 push한 값에 k 더하기. 더한 값이 n보다 크다면 n 빼기
  • 연산 결과값이 중복되기 때문에 문제 생김 (반례 2 2, 3 3, 10 2 등등)
  • index 같은게 필요할 것 같았고, "질문 검색" 보니 list로 구현 가능했다!
•  두 번째 시도:
  • iteration 사용하기 위해 list STL
  • 숫자를 우선 리스트에 다 넣어두고 시작 (이미 출력된 것들 중에 중복되는 숫자를 고려할 필요 없어짐)
  • iteration 증가를 반복할 때 range를 잘못 설정해서 자꾸만 k+1 번째를 출력했었다. for 조건 바꿔주니 해결 완료!
  • erase 한 후에 만약 list의 마지막 element를 지워줬다면, 다시 앞으로 돌아오게 하는 조건문을 빼먹으니 또 문제가 생겼었음
  • 아래 코드에 주석으로 설명을 추가했음
• "질문 검색"에 deque 사용하는 방법도 있던데, 다음 번에 도전

 

4. 코드

#include <iostream>
#include <list>

using namespace std;

list<int> l;

int main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int i, n, k = 0;
    
    cin >> n;
    cin >> k;
    
    for (i = 1; i <= n; i++){
    	// 숫자 순서대로 리스트에 넣기
        l.push_back(i);
    }
    
    // 첫 번째 element를 가르킨다
    list<int>::iterator iter = l.begin();
    
    cout << "<";
    while (l.size() != 1){ // 리스트에 마지막 원소를 남겨두기 전까지 반복
        for (i = 1; i < k; i++){ // k번째를 가르킨다
            iter++; // k번째가 될 때까지 1 증가
            if (iter == l.end()){ // 만약 리스트의 끝을 가르킨다면
                iter = l.begin(); // 원을 이루고 있으니 다시 앞으로
            }
        }
        cout << *iter << ", "; // 남은 숫자 중에 k번째 숫자 출력
        
        // 출력한 숫자 지우기
        iter = l.erase(iter); // 지워진 element의 다음을 가르킨다
        if (iter == l.end()){ // 만약 리스트의 끝에 도달했다면
            iter = l.begin(); // 한 바퀴 돌아 다시 가장 앞으로
        }
    }
    cout << *iter << ">\n"; // 마지막에 남은 숫자 출력
    
    return 0;
}