백준 1158 요세푸스

리스트와 vector

• vector
  - 연속적 메모리
  - 개별 원소 접근, 검색 빠름
  - 일반 배열에 비해 시작과 끝에 원소 추가 빠름 O(1)
  - 하지만 시작과 끝이 아닌 원소 삽입/제거시 느림 O(N)
• list
  - 비연속적 메모리
  - 특정 원소 접근하려면 처음이나 끝부터 선형탐색해야 한다.
  - 어느 위치든 삽입 / 제거 빠르다.
  - 접근 느리다. 각 노드가 앞과 뒤 주소만 가지고 있기 때문

즉, 중간에 삽입과 삭제가 계속 이루어지면 연결리스트 이용
길이가 정해지지 않은 배열이면 vector 이용

연결리스트와 벡터를 이용한 풀이

#include <bits/stdc++.h>
using namespace std;

int N, K, len = 0;



// 리스트에서 이전 노드 / 다음 노드를 가리키는 변수
int pre[5001];
int nxt[5001];
// 요세푸스 순열을 저장하는 변수
vector<int> v;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> K;

    // 원형 연결 리스트 생성
    // 맨 처음 노드와 마지막 노드가 서로를 가리키도록 지정
    for(int i = 1; i <= N; i++) {
        pre[i] = (i == 1) ? N : i-1;
        nxt[i] = (i == N) ? 1 : i+1;
        ++len;
    }

    // i는 순서, cur은 현재 숫자
    int i = 1;
    // 연결 리스트를 순회하며 순열 생성
    for(int cur = 1; len != 0; cur = nxt[cur]) {
        // K 번째일 때 제거
        if(i == K) {
            pre[nxt[cur]] = pre[cur];
            nxt[pre[cur]] = nxt[cur];
            v.push_back(cur);
            i = 1;
            --len;
        } else ++i;
    }

    // 요세푸스 순열 출력
    cout << "<";
    for(size_t i = 0; i < v.size(); i++) {
        cout << v[i];
        if(i != v.size() - 1) cout << ", ";
    }
    cout << ">";
}

vector를 이용한 풀이

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N, K;
    cin >> N >> K;
    vector<int> V, ans;

    for(int i = 1; i <= N; i++) V.push_back(i);

    for(int i = 0; ans.size() < N; i++) { // 정답 벡터에 n개의 원소가 쌓이면 종료
        if(i % K == K-1) ans.push_back(V[i]);  // K번째 사람일 때
        else V.push_back(V[i]);
    }
    cout << "<";
    for(int i = 0; i < N; i++) {
        if(i == N-1) cout << ans[i];
        else cout << ans[i] << ", ";
    }
    cout << ">";
}

구현방법도 구현방법이지만
i % K == K - 1 이라는 조건식을 도대체 어떻게 도출해냈을까..
대단하다