알고리즘/codeforces

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

falconlee236 2021. 11. 27. 09:47
반응형

문제 설명

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

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

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

  1. 임의의 위치 lr(1≤<rn)을 선택한다.
  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] 를 얻는다.

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

Input
첫번째 줄은 테스트케이스의 수 t(1t1000)가 주어진다.
다음 2t개 줄은 테스트 케이스의 설명이 이어진다.
각 테스트 케이스의 첫번째 줄에는 배열의 길이 n(2n50)이 주어진다. 두번째 줄에는 배열의 원소 ai(109ai109) 가 공백을 기준으로 주어진다. 배열 a의 원소는 중복이 가능하다.

Output
각 테스트 케이스마다 답을 출력한다.
답의 첫번째 줄은 주어진 배열을 정렬하기 위해서 필요한 연산의 개수 k(0kn) 이 주어진다. 다음 k개 줄에는 원형 이동을 하기 위해서 선택한 범위 lr(1l<rn), offset 값 d(1drl)을 "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(n2)의 시간 복잡도를 가지고 있어서 잘 안쓰지 않아요? 라고 말할 수 있지만 이럴때 문제의 조건을 유심히 봐야한다.
문제에서 테스트케이스가 최대 1000개이고, 원소의 개수가 최대 50개이다. 시간 복잡도가 O(n2) 인 삽입 정렬을 썼을 때, 최대 2500번의 연산이 이루어지고, 2500×1000=2500000 2백 5십만번 밖에 연산이 안 이루어지기 때문에 1억번의 연산이 1초라고 가정하면 시간 제한안에 무조건 문제를 풀 수 있다.

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

이때 원형 이동 연산은 다음과 같이 구현한다. 기준 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;
}
반응형