[백준 27979번] 볼링장 아르바이트 (C++)

문제링크 : https://www.acmicpc.net/problem/27979

27979번: 볼링장 아르바이트

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

vector<int>arr;
vector<int>arr2;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    for(int i=0; i<N; i++)
    {
        int num;
        cin >> num;
        arr.push_back(num);
        arr2.push_back(num);
    }

    sort(arr2.begin(), arr2.end());

    int cnt = 0;

    while(true)
    {
        if(arr.empty()) break;  //벡터가 비면 종료
        if(arr2.back() > arr.back())  //정렬된 값보다 작으면
        {
            cnt++;  //앞으로 옮겨야 하므로 카운트 증가
            arr.pop_back();
            continue;
        }

        if(arr2.back() == arr.back()) 
        {
            arr2.pop_back();
            arr.pop_back();
            continue;
        }
    }

    cout << cnt;

    return 0;

}

기존배열과 기존배열을 정렬한 배열을 두고 비교를 한다.

 

정렬된 제일 뒷값은 제일 큰 값이 와야 하므로 기존 배열과 비교하여 맨 뒷값에 정렬된 배열 값보다 작은 값이 있다면 그 값은 앞으로 옮겨야 하므로 카운트를 증가시킨다.

앞으로 보냈으면 해당 값은 이제 고려할필요가 없으므로 벡터내에서 없애준다.

그리고 만약 기존 배열과 정렬된 배열의 마지막 값이 서로 일치한다면 문제없으므로 카운트는 증가시키지 않고, 해당 값은 탐색이 끝난 것이기 때문에 기존 배열과 정렬된 배열 모두 해당 값을 없애준다.

 

이런식으로 맨 뒷값을 날리면서 정렬된 배열보다 작은 값이 있는지 확인하고, 기존 배열이 비게 되면 더 이상 탐색할 값이 없는  것이므로 반복문을 종료한다.