백준 10975번 데크 소트2 [C++]

 

 

 

 

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

 

#문제 간단 정리

 

구현 + 그리디라고 볼 수 있다.

 

 

#문제 해결 방법

 

우선 문제를 읽고 각 입력으로 

숫자가 주어졌을 때

 

덱을 어떻게 최소한으로 써야되는지 알아내는 문제이다

 

우선 입력은 3 6 0 9 5 4 

이렇게 주어지고

 

이 숫자들을 정렬했을 때는

0 3 4 5 6 9 임을 알 수 있는데

 

여기서 처음에 주어지는 3과 6을 보면

 

0 3 4 | 5 6 9

 

이렇게 각자 절반에 절반씩 띄워진 숫자라는 걸 알 수 있다.

 

여기서 만약에 입력이 다르게 온다고 생각을 해보면

 

예를 들어서 0 3 4 5 6 9 로 

주어진다고 생각해보면

 

정렬했을때도 연속되기 때문에 하나의 덱에 앞뒤로 값을 넣으면 되기 때문에 

당연히 덱을 하나 더 만들 필요가 없다는 걸 알게 된다.

 

그러나 정렬됫을때 연속된 숫자가 아니라 한칸 이상 띄어진 숫자로 주어진다면

ex) 0 3 4 5 6 9 에서  0 -> 3 으로 입력되면 덱이 더 필요없지만

0 -> 5 혹은 6으로 주어진다면 결국에 

같은 덱에 넣게 되면 

중간에 3과 4가 들어가줘야 되기 때문에 덱이 하나 더 필요함을 알 수 있다.

 

이제 대략 해결법이 나왔다.

 

주어진 수열에서 인덱스를 기억해두고

정렬해둔 다음에

 

기존 인덱스 별로 조회를 해서 만약

정렬했을 순서의 앞 뒤의 숫자중 하나를 이미 조회 한 적이 있다면 덱이 더 필요 없음

-> 이미 존재하는 덱에 추가해주면 되기 때문

 

만약 앞 뒤의 숫자가 조회한적이 없다면

중간에 삽입해줘야 하는 숫자가 존재하기 때문에 덱이 하나 더 필요함

 

라는 구성으로 구현을 하면 된다.

 

이제 구현으로 넘어가서 

인덱스를 따로 기록해주고

 

정렬을 한 다음에 

이 인덱스별로 조회를 하면서 방문배열을 기록해줘야 하는데

 

아마 이 과정이 귀찮기 때문에 구현 태그가 붙은 것 같다.

 

일단 n이 50밖에 안되기때문에

 

50을 한번씩 조회하면서 인덱스를 1부터 50까지 찾아도

50 * 50 = 250 밖에 안되기 때문에 

그냥 2중 반복문을 사용하였다

 

인덱스 1~n 까지 반복문

정렬된 숫자를 반복하면서 그 인덱스를 찾는 반복문

대략 이렇게 구현했다.

n이 작기 때문에 어떻게 구현하든 자유로울 것 같다.

 

#전체 코드

 

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    if (n == 1) {
        cout << 1; return 0;
    }

    vector<pair<int,int>> vec(n); // 값 , 인덱스
    for (int i = 0; i < n; i++) {
        cin >> vec[i].first;
        vec[i].second = i;
    }

    int ans = 0;

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

    vector<bool> visited(n, false);



    for (int i = 0; i < n; i++) { //총 n 개를 정렬해야함

        // i 번째 입력 으로 들어왔을때 , 정렬했을때 앞 뒤 값이 이미 방문했는지
        for (int j = 0; j < n; j++) {
            if (vec[j].second == i) { //i번째 인덱스
                visited[j] = true;
                if (j == 0) {
                    if (visited[j + 1] == false) ans++;
                }
                else if(j == n-1 ){
                    if (visited[j - 1] == false)  ans++;
   
                }
                else if (visited[j - 1] == true || visited[j + 1] == true) {

                }
                else {// 앞 뒤 값이 조회 안됬으면 중간에 값이 있으니 덱 하나 더 필요함
                    ans++;
                }
            }
        }

    }

    cout << ans << '\n';

    return 0;
}