[백준/BOJ] 10975. 데크 소트 2 [Gold 5]

10975. 데크 소트 2

문제출처 : https://www.acmicpc.net/problem/10975

code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int i,j, N, x, result = 0;
    vector<int> arr;
    vector<int> sortedarr;

    cin >> N;
    for (i = 0; i < N; i++)
    {
        cin >> x;
        arr.push_back(x);
        sortedarr.push_back(x);
    }
    
    sort(sortedarr.begin(), sortedarr.end());
    
    for (i = 0; i < N; i++)
    {
        for (j = 0; j < N; j++)
            if (arr[i] == sortedarr[j])
            {
                sortedarr[j] = 1001;
                break;
            }

        if (j == 0)
        {
            if (sortedarr[j + 1] != 1001)
                result++;
        }
        else if (j == N - 1)
        {
            if (sortedarr[j - 1] != 1001)
                result++;
        }
        else if (sortedarr[j - 1] == 1001 || sortedarr[j + 1] == 1001)
        {
            continue;
        }
        else
            result++;
    }

    cout << result;

    return 0;
}

이 문제 덕분에 데크라는 자료구조를 배우게 되었다.
데크는 큐와 비슷한 자료구조인데,
한쪽에서만 푸쉬 팝할 수 있는 큐와는 달리
데크는 양쪽에서 푸쉬 팝 할 수 있는 자료구조이다.

벡터를 처음 다룰 때 과연 내가 유용하게 쓸 수 있을까? 했는데, 지금은 일반 배열보다 벡터를 더 많이 쓰고 선호하는것같다.

데크 자료구조도 앞으로 필요할때 십분 활용해야 겠다.

요즘 블로그 포스팅이 많이 안되는것 같은데, 마침 감기도 걸렸겠다(코로나X) 집에서 착실하게 문제풀면서 잡담도 포스팅하고 해야겠다 ㅎㅎ

개강이 얼마남지않았다 ㅠㅠ

문제이름은 데크소트이지만, 푸는 방식이 그리디하기 때문에 그리디알고리즘에다 넣겠다.