[BAEKJOON] NO.2960 에라토스테네스의 체

https://www.acmicpc.net/problem/2960

처음에 이 문제를 보고 배열을 써서 해야겠다고 생각했다.

그런데 생각하다보니 위 사진의 알고리즘에서 '지운다'를 하려면
배열을 재정렬하거나, 다른 숫자로 마킹을 하거나 해야한다는 생각이 들어
갑자기 복잡해졌다(?)

C와 달리 C++에선 리스트를 그냥 사용할 수 있다는 게 떠올랐고,
처음으로 C++에서 제공하는 리스트를 써보게 되었다.

C++리스트 참고 블로그
(처음 써보는 와중에 위 블로그에서 많은 정보를 얻었다!)

리스트를 써보면서 하느라 이 문제는 1시간 정도 걸렸다ㅜㅜ
오래 걸렸다는 점이 아쉽지만 리스트를 활용했다는 거에 의의를 두려고 한다.

그리고 리스트로 푼 다음에는 배열로도 풀어봤다.
자료구조 하나 바꿨을 뿐인데 변수도 여러 개 추가되고 개인적으로 더 복잡하게 풀렸다..

CODE (ver.List)

#include <iostream>
#include <list>
using namespace std;

int main()
{
    int input_n, input_k;
    list<int> iList;

    // 입력받기
    cin>>input_n>>input_k;

    int size = input_n-1;
    int start_num = 2;
    
    // 값 집어넣기 
    for(int i=0; i<size; i++)
    {
        iList.push_back(start_num++);
    }

    int count = 0;
    int answer = 0;
    int tmp = 0;
    while(iList.size() > 0)
    {
        // 1. 가장 작은 수 찾기
        int min_num = iList.front();
        for (int i = 0; i < size; i++)
        {
            if (min_num > iList.front())
            {
                min_num = iList.front();
            }
        }
        // 2. 가장 작은 수 삭제
        tmp = iList.front();
        iList.pop_front();
        count++;
        if (count == input_k)
        {
            answer = tmp;
        }
        list<int>::iterator it = iList.begin();
        // 3. 가장 작은 수의 배수 삭제
        while (it != iList.end())
        {          
            if (*it % min_num == 0)
            {
                // cout << *it << "delete" << endl;
                tmp = *it;
                iList.erase(it++);
                count++;
                if(count == input_k)
                {
                    answer = tmp;
                }
            }
            else
            {
                // cout << *it << "no delete" << endl;
                it++;
            }
        } 
    }

    cout << answer << endl;

/* 출력 코드 */
//     iList.sort();
//     list<int>::iterator print_iter = iList.begin();
//    // 값이 잘 들어갔는지 출력
//     for(print_iter=iList.begin(); print_iter != iList.end(); print_iter++)
//     {
//         cout<<*print_iter<<" ";
//     }
//     cout<<endl<<"print completed"<<endl;
    
}

CODE (ver.Array)

#include <iostream>
#include <list>
using namespace std;

int main()
{
    int input_n, input_k;
    
    // 입력받기
    cin>>input_n>>input_k;

    int size = input_n-1;

    int * arr = new int[size];
    int start_num = 2;

    // 값 집어넣기 
    for(int i=0; i<size; i++)
    {
        arr[i] = start_num++;
    }

    int delete_count = 0;
    int answer = 0;
    int tmp = 0;
    int delete_Idx = 0;
    int count = size;
    
    int min_num = arr[0];
    int start = 0;
    while(count > 0)
    {
        // 1. 가장 작은 수 찾기
        for (int i = start; i < size; i++)
        {
            if (arr[i] != -1)
            {
                min_num = arr[i];
                delete_Idx = i;
                break;
            }
        }

        // 2. 가장 작은 수 삭제
        tmp = arr[delete_Idx];
        arr[delete_Idx] = -1;
        delete_count++;
        count--;
        if (delete_count == input_k)
        {
            answer = tmp;
            break;
        }
        

        // 3. 가장 작은 수의 배수 삭제
        for (int j = 0; j < size; j++)
        {
            if (arr[j] % min_num == 0)
            {
                if (arr[j] != -1)
                {
                    tmp = arr[j];
                    delete_count++;
                    count--;
                    if (delete_count == input_k)
                    {
                        answer = tmp;
                        break;
                    }
                    arr[j] = -1;
                }
            }
        }

        if (delete_count == input_k)
        {
            break;
        }
        
        start++;
        delete_Idx = start;
    }

    cout<<answer<<endl;

    delete [] arr;
    return 0;
    
}