[코드트리] 원형 수열에서의 인원 제거

 

 

---

 

문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

개념

큐

 

 

실행 결과

 

 

 

 

 

구현 코드(c++)

#include <iostream>
#include <queue>
using namespace std;

int main() {
  int n, k;
  cin >> n >> k;

  queue<int> q;

  for (int i = 1; i <= n; i++) {
    q.push(i);
  }

  while (q.size() != 1) {
    // 앞 사람들을 뒤로 보내기
    for (int i = 0; i < k - 1; i++) {
      q.push(q.front());
      q.pop();
    }

    // k 번째 사람 출력 후 제거 
    cout << q.front() << " ";
    q.pop();
  }

  // 남은 1명 출력
  cout << q.front();

  return 0;
}

 

 

 

 

코드 설명

원형 수열은 뒤에서 앞으로 다시 돌아가는 구조이므로

선입선출의 구조를 가진 자료구조 queue를 이용해 구현한다.

 

먼저 k번째에 위치한 사람 한 명만 남을때까지 앞에서부터 계속 push하면서 빼낸다.

한 명만 출력하고 다시 이 과정을 반복한다.

계속 제거하다보면 size가 1일 때 더 이상 제거가 불가능하므로 마지막 사람 출력 후 마무리.

 

 

---