[BOJ 1158] 요세푸스 문제

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

1158번: 요세푸스 문제

문제 분석

• 제한 시간은 널널한 편이다.(2초)
• 지난 번에 풀었던 2346번,"풍선 터뜨리기 문제"(https://genius00hwan.tistory.com/58) 가 생각난다.
• 그 문제와 비슷한 논리로 풀어봐야 겠다.
• 계획:
  <deque> 자료구조를 사용한다.
  deque가 비어있을 때 까지 아래를 반복한다.
  
  • deque 맨앞에 있는 값을 맨뒤로 넣어주는 행위를 k-1 번 반복한다.
    (재귀함수안에 반복문을 넣는게 바람직하지는 않겠지만 제한시간이 널널하니까 이렇게 해도 될거 같다.)
  • 맨앞에 있는 값을 출력하고, 삭제한다.
• 주의사항:
  출력할 때"<.,.,...,.,.>"형식으로 출력한다.

deque<int> people; //요세푸스 순열
int n, first; 

void cycle(int x) {
    int m = x - 1;
    while (m--) { // x - 1 번 반복
        people.push_back(people.front()); 
        people.pop_front(); 
        //맨 앞에 값 빼서 뒤에 추가
    }
    cout << people.front();// 맨 앞에 값(x번째 값) 출력
    people.pop_front();// 맨 앞에 값(x번째 값) 제거
    if (people.empty()) return;//deque가 비면 그만!
    else cout << ", ";//다음 값 있으면 "," 출력
    cycle(x);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> first;
    for (int i = 1; i <= n; i++) { //인원수 만큼 1부터 deque에 삽입
        people.push_back(i);
    }

    cout << "<";// 출력 시작전 "<"출력
    cycle(first); // 첫 값은 입력된 값
    cout << ">";// 출력 마치고 ">"출력
    return 0;
}

느낀 점

• 이 문제를 풀면서 가장 크게 느낀 감정은 뿌듯함이다. 유사한 문제를 풀어본 경험으로 쉽게 문제를 해결했다.
• 출력할 때"<.,.,...,.,.>"형식으로 출력한다는 점이 좀 고민됐는데 출력할때 쉼표를 같이 출력하면 되겠다는 생각이 들었다.
  하지만 출력할 때마다 쉼표를 같이 출력하게 되면 마지막 값을 출력 할 때도 쉼표를 출력하게 된다.
  그래서 재귀함수를 멈추기 위한 if (people.empty()) 문을 이용해 다음값이 있으면 ","를 출력하게 했다.
  (이 부분이 꼼수인지 묘수인지 모르겠지만 좀더 예쁜 답이 있지 않을까하는 생각이든다...ㅎㅎ)

시간 복잡도

• 1~n까지에 숫자 deque에 삽입 →O(n)
• deque 맨앞에 있는 값을 맨뒤로 넣어주는 while문 → O(n)(최악의 경우)
• 재귀함수 반복 → O(n)
  ➣O(n^2)