문제 설명
차세대 외부 메모리에는 정수의 배열
이 종류의 메모리는 배열의 원소를 바꿀수가 없게 만들어졌다. 대신에 주어진 배열의 일부분을 자르고, 그 부분에 있는 원소들을 주어진 offset만큼 원형 이동시킨다.
기술적으로 각 원형 이동은 두가지 연속적인 단계로 이루어진다.
- 임의의 위치
과 을 선택한다. 부분을 왼쪽으로 임의의 offset 만큼 원형 이동 시킨 결과로 바꾼다. 원형 이동이란 다음 설명으로 이해할 수 있다. 순열 은 을 offset 1만큼 왼쪽으로 원형 이동 시킨 결과이다. 순열 은 순열 을 왼쪽으로 offset 2만큼 원형 이동 시킨 결과이다.
예를 들어 만약
우리가 해야할 것은 주어진 배열
Input
첫번째 줄은 테스트케이스의 수
다음
각 테스트 케이스의 첫번째 줄에는 배열의 길이
Output
각 테스트 케이스마다 답을 출력한다.
답의 첫번째 줄은 주어진 배열을 정렬하기 위해서 필요한 연산의 개수
정렬에 필요한 최소 원형 이동 개수를 찾는 것이 아니며, 원형 이동 횟수가
만약 주어진 배열
만약 여러 가능한 답이 있다면 그중 하나만 출력한다.
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
정렬을 처음 공부할 때 배우는 내용인 삽입정렬의 과정을 이해하고 있으면 쉽게 풀 수 있는 문제이다. 삽입 정렬은
문제에서 테스트케이스가 최대 1000개이고, 원소의 개수가 최대 50개이다. 시간 복잡도가
문제를 푸는 아이디어는 삽입 정렬을 수행하는 과정과 같고 거기에 몇가지 과정을 추가한다. 첫번째 index를
만약 첫번째 index보다 작은 값이 존재하면 그 index를
만약 첫번째 index보다 작은값이 존재하지 않다면 이미
이 과정을
이때 원형 이동 연산은 다음과 같이 구현한다. 기준 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;
}
'알고리즘 > codeforces' 카테고리의 다른 글
Codeforces Round #744 (Div. 3)-D. Productive Meeting (0) | 2021.11.27 |
---|---|
Codeforces Round #744 (Div. 3)-C. Ticks (0) | 2021.11.27 |
Codeforces Round #744 (Div. 3)-A. Casimir's String Solitaire (0) | 2021.11.27 |
Codeforces Round #748 (Div. 3)-E. Gardener and Tree (0) | 2021.11.25 |
Codeforces Round #748 (Div. 3)-D1. All are Same (0) | 2021.11.25 |