알고리즘 공부 4

lsh235·2024년 10월 12일
0

CodingTest

목록 보기
11/31

Array

문제 : 백준 1158-요세푸스 문제

생각한 구현 내용

  1. 1부터 N까지의 숫자를 백터에 넣는다.
  2. 반복을 돌면서 N의 백터가 다 비워질때까지 K번째 숫자를 다른 리스트에 추가한다.
  3. 마지막 한개를 리스트에 추가하여 리스트를 전부 출력한다.

알게 된 점

  1. 원형 계산, 끝에 도달하면 다시 처음으로 돌아가야하는 경우에는 모듈러 연산이 필요하다.
    모듈러 연산의 특징
    나머지 값의 범위는 항상 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>

핵심

  1. 원형 계산, 끝에 도달하면 다시 처음으로 돌아가야하는 경우에는 모듈러 연산이 필요하다.
  2. 모듈러 연산 로직
    next_index = (now_index + K(select_index) - 1) % now_queue_size

0개의 댓글