백준 13884 - 삭삽 정렬

문제 설명

선종이는 최근에 배열을 정렬하는 새로운 알고리즘을 이길흥 교수님의 강의에서 배웠습니다. 그 알고리즘은 배열의 숫자들을 반복적으로 삭제, 삽입을 수행하여 배열을 정렬합니다. 선종이는 이 정렬 알고리즘을 삭삽 정렬이라 이름 붙였습니다. 삭삽 정렬은 다음과 같은 과정을 수행합니다.

1. 배열의 요소 하나를 선택합니다.
2. 배열에서 해당 요소를 삭제합니다.
3. 해당 요소를 배열의 맨 뒤에 삽입합니다.

선종이는 호기심이 많은 학생이기 때문에, 삭삽 정렬을 수행하여 배열을 정렬 할 때 가장 적게 위와 같은 삭삽 과정이 얼마나 수행되는지 알아보고 싶어졌습니다.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 배열이 주어졌을 때 하나의 숫자를 택해 제일 뒤로 보내는 연산을 수행하여 정렬해야 한다.

이때, 최소 연산 수를 구해야 한다.

 

간단하게 생각해 보면 가장 작은 수부터 선택해서 하나씩 뒤로 보내면 정렬이 완성된다.

즉, 최대 배열의 길이만큼 수행하면 정렬이 된다.

여기서 연산을 줄이는 방법이 존재한다.

이미 정렬된 숫자들은 굳이 뽑아서 뒤로 보낼 필요가 없다.

예를 들어 보자.

1 5 2 4 3 6

여기서 1, 2, 3 은 이미 정렬된 순서대로 배치되어 있다.

즉, 4, 5, 6만 뽑아내어 뒤로 보내면 된다.

 

따라서, 주어진 배열을 정렬한 뒤 올바른 순서대로 배치된 숫자의 개수를 세어 전체 개수에서 빼주면 뒤로 보내야 할 숫자의 개수를 구할 수 있다.

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int T, N;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout << fixed;
    cout.precision(4);

    cin >> T;

    while (T--)
    {
        int K;
        cin >> K >> N;

        vector<int> origin(N);
        vector<int> nums(N);

        int minNum = INT_MAX;
        for (int i = 0; i < N; i++)
        {
            cin >> nums[i];
            origin[i] = nums[i];
            minNum = min(minNum, nums[i]);
        }

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

        //정렬되어 있는 숫자들 파악
        int target = minNum;
        int cursor = 0;
        for (int i = 0; i < N; i++)
        {
            if (target == origin[i])
            {
                target = nums[++cursor];
            }
        }

        cout << K << " " << N - cursor << "\n";
    }


    return 0;
}

---