- 1부터 N까지의 숫자를 백터에 넣는다.
- 반복을 돌면서 N의 백터가 다 비워질때까지 K번째 숫자를 다른 리스트에 추가한다.
- 마지막 한개를 리스트에 추가하여 리스트를 전부 출력한다.
- 원형 계산, 끝에 도달하면 다시 처음으로 돌아가야하는 경우에는 모듈러 연산이 필요하다.
모듈러 연산의 특징
나머지 값의 범위는 항상 0부터 (나누는 수 - 1)까지입니다.예를 들어, 배열의 크기가 7이고 현재 인덱스가 5일 때, K = 3이라면 5 + 3 = 8이지만 배열의 크기를 넘어섰으므로 1번째 인덱스로 돌아가야 합니다.
인덱스 계산: (현재 인덱스 + K - 1) % 배열 크기
(5 + 3 - 1) % 7 = 0 → 첫 번째 인덱스로 돌아감.배열 크기가 7이고, 현재 인덱스가 6일 때 K=3라면:
(6 + 3 - 1) % 7 = 8 % 7 = 1 → 두 번째 인덱스로 돌아감.next_index = (now_index + K(select_index) - 1) % now_queue_size
1 2 3 4 5 6 7
1 2 [3] 4 5 [6] 7 -> <3, 6>
1 2 [4] 5 7 -> <3, 6, 4>
1 2 [5] 7 -> <3, 6, 4, 5>
...
과 같은 구조로 해결되는 문제로 이해했다.
#include <bits/stdc++.h>
using namespace std;
int main(void) {
// 입출력 분리해서 빠르게 동작하도록
ios::sync_with_stdio(0);
cin.tie(0);
// 공백을 기준으로 N K 파싱
int N, K;
cin >> N >> K;
vector<int> num_list;
for (int i = 1; i <= N; ++i) {
num_list.push_back(i);
}
vector<int> num_result;
int idx = 0;
while (!num_list.empty()) {
idx = (idx + K - 1) % num_list.size();
num_result.emplace_back(num_list[idx]);
num_list.erase(num_list.begin() + idx);
}
cout << "<";
for (size_t i = 0; i < num_result.size(); ++i) {
if (i != 0)
cout << ", ";
cout << num_result[i];
}
cout << ">" << endl;
return 0;
}
첫 번째 제거:
now_index = 0
(index + K - 1) % size = (0 + 3 - 1) % 7 = 2
people[2] = 3이 제거됩니다.
남은 사람: [1, 2, 4, 5, 6, 7]
결과: <3>
두 번째 제거:
now_index = 2
(2 + 3 - 1) % 6 = 4
people[4] = 6이 제거됩니다.
남은 사람: [1, 2, 4, 5, 7]
결과: <3, 6>
세 번째 제거:
now_index = 4
(4 + 3 - 1) % 5 = 1
people[1] = 2가 제거됩니다.
남은 사람: [1, 4, 5, 7]
결과: <3, 6, 2>
네 번째 제거:
now_index = 1
(1 + 3 - 1) % 4 = 3
people[3] = 7이 제거됩니다.
남은 사람: [1, 4, 5]
결과: <3, 6, 2, 7>
다섯 번째 제거:
now_index = 3
(3 + 3 - 1) % 3 = 2
people[2] = 5가 제거됩니다.
남은 사람: [1, 4]
결과: <3, 6, 2, 7, 5>
여섯 번째 제거:
now_index = 2
(2 + 3 - 1) % 2 = 0
people[0] = 1이 제거됩니다.
남은 사람: [4]
결과: <3, 6, 2, 7, 5, 1>
마지막 제거:
now_index = 0
people[0] = 4가 제거됩니다.
남은 사람: []
결과: <3, 6, 2, 7, 5, 1, 4>