boj 1517 버블 소트

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

 

예전에 재채점되어 틀린 문제를 다시 풀게 되었습니다.

 

덕분에 이 글은 내리게되었네요 ㅠ

이전에는 merge sort로 풀었던 문제라 그건 수정해서 AC를 받았고, 이번에는 다른 방법으로 접근했습니다.

 

이 문제처럼 버블 소트의 특징을 이해하고 있다면 해결할 수 있습니다.

버블소트는 앞뒤의 수를 비교하여 앞의 숫자가 크면 두 수의 위치를 swap 하게 됩니다.

이 문제는 그 swap의 횟수를 구하는 문제로 본인보다 앞에 있지만 더 큰수의 갯수를 세어주면 된다는 결론이 나옵니다.

 

그러면 입력으로 주어지는 정수들로 세그먼트 트리를 이용할 수 있습니다.

본인보다 먼저 트리에 들어간 수 중에 본인보다 큰 수의 갯수를 카운팅하도록 합니다.

하지만 입력의 범위는 절댓값이 10억이라서 배열로 표현하기는 어려울 수 있습니다.

그렇다면 N이 50만이라는 것을 이용하여 좌표압축 기법을 생각할 수 있습니다.

 

https://whyeskang.com/362

좌표 압축 (Coordinate Compression)

위 게시글을 참고하시면 문제없이 좌표압축 기법을 사용하실 수 있을 것입니다.

 

좌표압축이 끝났다면 1 ~ N의 범위 내에서 본인보다 큰 수의 갯수를 세그먼트 트리를 활용하여 구할 수 있습니다.

입력이 들어온 순서대로 query 함수를 이용하여 갯수를 구하고, update를 시켜주면 차례대로 구할 수 있습니다.

 

 

[C++]

#include <iostream>
#include <algorithm>
#define MAX 500001
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
 
pii list[MAX];
ll tree[MAX << 2];
int N;
 
void compress() {
    sort(list, list + N);
    int pre = 1e9 + 1;
    int cnt = 0;
    for (int i = 0; i < N; i++) {
        if (pre != list[i].first) cnt++;
        pre = list[i].first;
        list[i].first = cnt;
    }
    sort(list, list + N, [](pii a, pii b) {
        return a.second < b.second;
    });
}
 
ll update(int node, int l, int r, int x) {
    if (x < l || r < x) return tree[node];
    if (l == r) return ++tree[node];
 
    int m = (l + r) >> 1;
    return tree[node] = update(node << 1, l, m, x) + update((node << 1) + 1, m + 1, r, x);
}
 
ll query(int node, int l, int r, int s, int e) {
    if (s <= l && r <= e) return tree[node];
    if (l > e || s > r) return 0;
 
    int m = (l + r) >> 1;
    return query(node << 1, l, m, s, e) + query((node << 1) + 1, m + 1, r, s, e);
}
 
void func() {
    compress();
 
    ll ret = 0;
    for (int i = 0; i < N; i++) {
        ret += query(1, 1, N, list[i].first + 1, N);
        update(1, 1, N, list[i].first);
    }
    cout << ret << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i].first;
        list[i].second = i;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}

 

Java로 문제를 풀다가 의문이 든게 있는데

 

Arrays.sort(array, from, to, comparator) 메소드와

Arrays.sort(array, comparator) 메소드의 성능 차이에 대해 궁금해졌습니다.

AC를 받은 코드는 Arrays.sort(array, from, to, comparator) 메소드를 사용한 코드고,

TLE를 받은 코드는 Arrays.sort(array, comparator) 메소드를 사용한 코드입니다.

그거 말고는 차이가 없는데 결과가 다르게 나오는 상황이라.. 당황했던 기억이 있습니다.

이걸 시스템상의 문제로 짚고 넘어가도 될만한 것인지는 잘 모르겠네요. 그냥 억까라고 해야하나 이걸

 

 

[Java]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
 
public class Main {
    private static int list[][];
    private static long tree[];
    private static int N;
 
    private static void compress() {
        Arrays.sort(list, 0, N, (o1, o2) -> {
            if (o1[0] == o2[0]) return o1[1] - o2[1];
            return o1[0] - o2[0];
        });
        int pre = Integer.MAX_VALUE;
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            if (pre != list[i][0]) cnt++;
            pre = list[i][0];
            list[i][0] = cnt;
        }
        Arrays.sort(list, 0, N, Comparator.comparingInt(o -> o[1]));
    }
 
    private static long update(int node, int l, int r, int x) {
        if (x < l || r < x) return tree[node];
        if (l == r) return ++tree[node];
 
        int m = (l + r) >> 1;
        return tree[node] = update(node << 1, l, m, x) + update((node << 1) + 1, m + 1, r, x);
    }
 
    private static long query(int node, int l, int r, int s, int e) {
        if (s <= l && r <= e) return tree[node];
        if (l > e || s > r) return 0L;
 
        int m = (l + r) >> 1;
        return query(node << 1, l, m, s, e) + query((node << 1) + 1, m + 1, r, s, e);
    }
 
    private static void func() {
        compress();
 
        long ret = 0;
        for (int i = 0; i < N; i++) {
            ret += query(1, 1, N, list[i][0] + 1, N);
            update(1, 1, N, list[i][0]);
        }
        System.out.println(ret);
    }
 
    private static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new int[N][2];
        tree = new long[(N << 2) + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            list[i][0] = Integer.parseInt(st.nextToken());
            list[i][1] = i;
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}