Codeforces Round #744 (Div. 3)-B. Shifting Sort

문제 설명

차세대 외부 메모리에는 정수의 배열 $a[1...n] = [a_1, a_2, ..., a_n]$이 포함되어 있다.

이 종류의 메모리는 배열의 원소를 바꿀수가 없게 만들어졌다. 대신에 주어진 배열의 일부분을 자르고, 그 부분에 있는 원소들을 주어진 offset만큼 원형 이동시킨다.

기술적으로 각 원형 이동은 두가지 연속적인 단계로 이루어진다.

1. 임의의 위치 $l$과 $r (1 \le < r \le n)$을 선택한다.
2. $a[l...r]$ 부분을 왼쪽으로 임의의 offset $d$만큼 원형 이동 시킨 결과로 바꾼다. 원형 이동이란 다음 설명으로 이해할 수 있다. 순열 $[1, 4, 1, 3]$은 $[3, 1, 4, 1]$을 offset 1만큼 왼쪽으로 원형 이동 시킨 결과이다. 순열 $[4, 1, 3, 1]$은 순열 $[3, 1, 4, 1]$을 왼쪽으로 offset 2만큼 원형 이동 시킨 결과이다.

예를 들어 만약 $a = [1, 3, 2, 8, 5]$ 이고, $l = 2, r = 4, d = 2$ 이면 $a[2...4] = [3, 2, 8]$ 부분이 튀어 나온다. 이 부분은 곧 offset $d = 2$만큼 왼쪽으로 원형 이동을 한다. 그리고 결과 값 $[8, 3, 2]$을 얻는다. 이 값을 원래 튀어나온 부분과 교체를 하면 $a = [1, 8, 3, 2, 5]$ 를 얻는다.

우리가 해야할 것은 주어진 배열 $a$를 $n$번의 원형 이동을 통해서 정렬을 하는 것이다. 이때 원형 이동 횟수를 최소화할 필요가 없다. 즉 어떤 식으로든 주어진 배열이 정렬된 상태이기만 하면 된다.

Input
첫번째 줄은 테스트케이스의 수 $t (1 \le t \le 1000)$가 주어진다.
다음 $2t$개 줄은 테스트 케이스의 설명이 이어진다.
각 테스트 케이스의 첫번째 줄에는 배열의 길이 $n(2 \le n \le 50)$이 주어진다. 두번째 줄에는 배열의 원소 $a_i(-10^9 \le a_i \le 10^9)$ 가 공백을 기준으로 주어진다. 배열 $a$의 원소는 중복이 가능하다.

Output
각 테스트 케이스마다 답을 출력한다.
답의 첫번째 줄은 주어진 배열을 정렬하기 위해서 필요한 연산의 개수 $k(0 \le k \le n)$ 이 주어진다. 다음 $k$개 줄에는 원형 이동을 하기 위해서 선택한 범위 $l$과 $r(1 \le l < r \le n)$, offset 값 $d(1 \le d \le r - l)$을 "$l; r ;d$"형식으로 출력해야 한다. 무조건 원형 이동은 offset $d$만큼 왼쪽으로 이동해야한다.

정렬에 필요한 최소 원형 이동 개수를 찾는 것이 아니며, 원형 이동 횟수가 $n$이 넘지 않는 정렬 방법이면 모두 통과한다.

만약 주어진 배열 $a$가 이미 정렬된 상태라면 $k = 0$을 출력하고 이후에 아무것도 출력하지 않는 방법도 한가지 답이 될 수 있다.

만약 여러 가능한 답이 있다면 그중 하나만 출력한다.

Example
input
4
2
2 1
3
1 2 1
4
2 4 1 3
5
2 5 1 4 3

output
1
1 2 1
1
1 3 2
3
2 4 1
2 3 1
1 3 2
4
2 4 2
1 5 3
1 2 1
1 3 1

문제 접근

사용한 알고리즘: 구현, 정렬
걸린 시간 : 00:11
정렬을 처음 공부할 때 배우는 내용인 삽입정렬의 과정을 이해하고 있으면 쉽게 풀 수 있는 문제이다. 삽입 정렬은 $O(n^2)$의 시간 복잡도를 가지고 있어서 잘 안쓰지 않아요? 라고 말할 수 있지만 이럴때 문제의 조건을 유심히 봐야한다.
문제에서 테스트케이스가 최대 1000개이고, 원소의 개수가 최대 50개이다. 시간 복잡도가 $O(n^2)$ 인 삽입 정렬을 썼을 때, 최대 $2500$번의 연산이 이루어지고, $2500 \times 1000 = 2500000$ 2백 5십만번 밖에 연산이 안 이루어지기 때문에 1억번의 연산이 1초라고 가정하면 시간 제한안에 무조건 문제를 풀 수 있다.

문제를 푸는 아이디어는 삽입 정렬을 수행하는 과정과 같고 거기에 몇가지 과정을 추가한다. 첫번째 index를 $i$라고 가정하자. 그렇다면 첫번째 index부터 시작해서 그 index와 나머지 원소를 비교한다.
만약 첫번째 index보다 작은 값이 존재하면 그 index를 $j$라고 할때 $i$와 $j$를 선택하고, 그 값의 차이만큼 왼쪽으로 이동하면 $0$부터 $i$번째 index까지 배열은 모두 정렬이 될것이다.
만약 첫번째 index보다 작은값이 존재하지 않다면 이미 $0$부터 $i$번째까지 배열은 모두 정렬이 된 상태이기 때문에 원형 이동 연산은 이루어지지 않는다.
이 과정을 $0$번째 원소부터 $n - 1$번째 원소까지 쭉 진행하고 답을 출력하면 된다.

이때 원형 이동 연산은 다음과 같이 구현한다. 기준 index보다 작은 값이 존재할 때, 최솟값을 배열에서 지운다. 그리고 그 값을 기준값의 앞에 삽입한다. 이런 방식으로 하면 원형 이동 연산을 완벽하게 구현 할 수 있다. 잘 이해가 안되는 사람은 진행 과정을 한 두번 노트에 적어보면 바로 이해가 될 것이다.

c++에서는 배열에서 지우는 연산과 삽입하는 연산을 각각 STL에 있는erase()와 insert()함수를 통해서 쉽게 구현할 수 있다.

정답 코드

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        vector<int> arr(n);
        vector<pair<int, int>> ans;
        for(int i = 0; i < n; i++) cin >> arr[i];

        for(int i = 0; i < n - 1; i++){
            int idx = i;
            for(int j = i + 1; j < n; j++){
                if(arr[idx] > arr[j]) idx = j;
            }

            if(idx == i) continue;
            int num = arr[idx];
            ans.emplace_back(i, idx);

            arr.erase(arr.begin() + idx);
            arr.insert(arr.begin() + i, num);
        }

        cout << ans.size() << "\n";
        for(auto x : ans) cout << x.first + 1 << " " << x.second + 1 << " " << x.second - x.first << "\n";
    }
    return 0;
}