[algospot] MEASURETIME

문제링크 입니다

🚀 [MEASURETIME] 삽입 정렬 시간 재기 문제 😊😊😊😊😊

유명한 정렬 알고리즘인 삽입 정렬은 정렬된 부분 배열을 유지하며 이 배열에 새 원소를 삽입해 나가는 식으로 동작합니다. 주어진 정수 배열 A를 정렬하는 삽입 정렬의 구현은 다음과 같습니다.

void insertionSort(vector<int>& A) {
  for(int i = 0; i < A.size(); ++i) {
    // A[0..i-1] 에 A[i] 를 끼워넣는다
    int j = i;
    while(j > 0 && A[j-1] > A[j]) {
      // 불변식 a: A[j+1..i] 의 모든 원소는 A[j] 보다 크다.
      // 불변식 b: A[0..i] 구간은 A[j] 를 제외하면 정렬되어 있다.
      swap(A[j-1], A[j]);
      --j;
    }
  }
}

삽입 정렬은 A[0..i-1] 이 정렬된 배열일 때, A[i] 를 적절한 위치를 만날 때까지 왼쪽으로 한칸씩 움직입니다. 예를 들어 A={5,1,4,3,2} 의 삽입 정렬은 다음과 같이 이루어집니다.

A	비고
51432	초기상태
15432	72
14532	4를 왼쪽으로 1칸 옮김
13452	3을 왼쪽으로 2칸 옮김
12345	2를 왼쪽으로 3칸 옮김

길이 N 인 수열 A[] 가 주어집니다. 이 정렬 과정에서 숫자들을 총 몇 번이나 옮기는지를 계산하는 프로그램을 작성하세요. 예를 들어 위 배열의 경우 총 1+1+2+3=7 번 숫자를 옮기게 됩니다.

🔑 [풀이]

삽입정렬을 이용해 횟수를 세는 방법을 사용하면 수열의 크기가 10만이기 때문에 시간내에 수행 할 수 없습니다. 이에 해법으로 펜윅트리를 사용합니다.
A의 각원소 A[i]에 대해 이 원소가 옆으로 몇 칸이나 움직일지를 계산하려면 A[0,,i-1] 구간에 A[i]보다 큰 숫자가 몇 개나 있는지를 알아야 합니다. 이를 위해 각 숫자의 출현 횟수를 저장하는 펜윅 트리를 만들어 문제를 해결합니다.

64비트 정수이기 때문 long long 타입을 사용해야합니다.

⌨️ 입력

입력의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 원 배열의 길이 N (1 <= N <= 50000) 이 주어집니다. 그 다음 줄에 N개의 정수로 A의 원소 Ai가 주어집니다. (0 <= Ai < 1,000,000)

입력의 양이 많으므로 가능한 빠른 입력 함수를 사용하는 것이 좋습니다.

🖥 출력

각 테스트 케이스마다 한 줄에 A를 삽입정렬하는 과정에서 숫자를 옮기는 총 횟수를 출력합니다.

🖱 입력 예제

2
5
5 1 4 3 2
10
7 8 6 6 1 9 4 4 3 10

💻 출력 예제

7
25

💎 전체 코드는 다음과 같습니다.

//
//  MEASURETIME.cpp
//  AALGGO
//
//  Created by inhyeok on 2021/12/29.
//

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


struct FenWickTree{
    vector<int> tree;
    FenWickTree(int n) : tree(n+1){}
    int sum(int pos){
        pos++;
        int result = 0;
        while(pos>0){
            result += tree[pos];
            pos &= (pos-1);
        }
        return result;
    }
    void add(int pos, int val){
        pos++;
        while(pos<tree.size()){
            tree[pos] += val;
            pos += (pos & -pos);
        }
    }
};

long long countMoves(const vector<int>& A){
    FenWickTree tree(1000000);
    long long ret=0;
    for(int i=0; i<A.size(); i++){
        ret += tree.sum(999999) - tree.sum(A[i]);
        tree.add(A[i],1);
    }
    return ret;
}

int main(){
    int test_case;
    cin >> test_case;
    for(int test=0; test<test_case; test++){
        int n;
        cin >> n;
        vector<int> result(n);
        for(int i=0; i<n; i++){
            cin >> result[i];
        }
        cout << countMoves(result) << endl;
    }
}