문제

문제링크

에라토스테네스의 체라는 문제다. n보다 작은 소수를 찾는 알고리즘인데, 알고리즘 순서는 다음과 같다.

풀이

저걸 그대로 구현하면되는데
탐색하면서 지우는 작업이 들어가있다.
이걸 배열이나 vector를 사용해서 푼다면 직접 지워서는 안된다.
지운다면 다시 배열을 만드는 작업이 n만큼의 시간이 걸리기 때문이다.
(n의 크기가 작아서 빅오가 커도 이번 문제는 그냥 맞을수도 있을거같다.)

그럼 지우지 않고 visited로 체크를 하면?
그것도 결국 순차탐색을 하면서 visited가 true인 false인지 체크해야해서
건널뛸수가없어 다시 n만큼의 탐색시간이 걸린다.

그래서 연결리스트로 접근해보기로 했다. 그러면 삭제해도 다시 한칸씩 땡기지 않으니 삭제 연산에서 시간 문제가 안생긴다. python으로 구현했을때는 내가 직접 linked list를 구현했는데 c++의 list는 양방향 연결리스트로 있어서 이를 사용해봤다.

근데 순차탐색할때 해당 원소를 지우면 다음은 어떻게 찾을까 고민했는데
다행히 li.erase() 함수를 쓰면 다음 원소의 포인터를 반환해준다.

또한 list는 반복자(iterator)를 통해 순차탐색해야한다.
list::iterator iter = li.begin() 같이 포인터로 접근하면 된다.
(auto iter 로 줄여서도 가능)

li.end()는 마지막 원소의 포인터가 아니라 마지막을 알려주는 포인터다.
그래서 마지막 원소의 포인터는 li.end()-- 가 된다.
순차탐색을 편하게 쓰기위함 같다.
ex) for(auto iter=li.begin();iter!=li.end();li++){...}

code

/**
 * 백준 2960
 * 구현
 * 에라토스테네스의 체
 * 배열보다는 리스트로
*/
#include <bits/stdc++.h>
using namespace std;

int n,k;
int cnt=0;
list<int> li;

bool eratos(){
    list<int>::iterator iter = li.begin();
    // auto iter=li.begin(); 로 줄여서 사용 가능
    int num=*iter;
    for(;iter!=li.end();iter++){
        if(*iter%num == 0){
            cnt++;
            if(cnt==k){
                cout<<*iter;
                return true;
            }
            iter=li.erase(iter);
        }
    }
    return false;
}

int main(void){
    // k는 n보다 작은수
    cin >>n>>k;

    // init
    for(int i=2;i<=n;i++){
        li.push_back(i);
    }
    while(!eratos()){}
}