(BOJ) 1158 풀이

#include<bits/stdc++.h>

using namespace std;
int nxt[5001];
int pre[5001];
int main(void){
    int N,K,count=1;
    cin >> N >> K;
    for(int i=1;i<=N;i++){
        nxt[i]=i==N?1:i+1;
        pre[i]=i==1?N:i-1;
    }
    int c=0;
    cout << '<';
    for(int cur=1;;cur=nxt[cur]){
        if(count++%K==0){
            c++;
            if(c==N){
                cout << cur << '>';
                    break;
            }
            cout << cur << ", ";
            nxt[pre[cur]]=nxt[cur];
            pre[nxt[cur]]=pre[cur];
        }
    }

}

참고로 지금 풀고있는 문제들은

https://justicehui.github.io/tutorial/,

https://github.com/encrypted-def/basic-algo-lecture/blob/master/workbook.md

위 두 링크를 위주로 풀고있습니다.

 

옛날에 풀려있었던 문제인데,

그 때는 1~N 을 모두 큐에 넣고, K 의 배수에 해당하는 위치의 숫자가 가 맨 앞에 올 떄 까지

앞에있는 숫자들을 뒤로 보내고, (K-1 번 반복하면 됨)

그 숫자를 출력한 뒤 pop

큐가 빌 때까지 반복하면 됨.

---

하지만 지금은 리스트를 배우고 있으니,

STL 원형리스트를 찾아봤는데 안나오길래

답지를 참고해서 소스를 짰다.

 

N 까지의 수들을 두 개의 배열을 통해 circular double linked list 형식으로 연결합니다.

count 를 1부터 1씩 증가시키면서 K 로 나누어 떨어질 떄,

현재의 cur 변수를 출력하고 cur 에 해당하는 노드를 unlink 합니다.

이 과정을 N 번하면 되니, 따로 카운트하는 c 변수를 만들어서 N 와 같을 때 종료.