boj 2517 달리기

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

2517번: 달리기

자신 앞에 있는 사람들 중 자신보다 실력이 더 낮은 사람이 몇 명인지 구하는 문제입니다.

이 문제는 두 가지 방법으로 해결하였습니다.

예전에 배운적 있었던 Merge Sort방법과 이 문제의 풀이방법으로 명시되어 있는 Segment Tree 방법으로 문제를 두번 풀어보았습니다.

 

먼저 Merge Sort 방법입니다.

평소의 Merge Sort를 사용했던 것처럼 i번과 j번을 서로 비교해가며 큰 값을 sorted[k]에 저장하는 방식입니다.

 

여기서 기존의 Merge Sort에 추가해야 할 것이 하나 있는데

i번은 앞의 인덱스, j번은 뒤의 인덱스 이므로 j번 인덱스의 값이 앞으로 이동하게 되면 그 차이만큼 rank에서 빼줍니다. (i번이 뒤로가는 것은 무시하셔도 됩니다.)

 

 

C++로 구현한 merge sort방식

JAVA로 구현한 merge sort방식

 

작년에 C++로 동일한 방식으로 해결하였으나 java에서는 TLE를 받았는데

아는 형님께서 StringBuilder라는 것을 알려주셨고, 출력 부분에 이것만 추가하니 AC를 받았습니다.

StringBuilder를 이제 자주 써야겠다는 생각이 드는군요 ㅎㅎ

오늘도 하나 배워갑니다..

 

 

[Merge Sort]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[][], rank[], sorted[][];
 
    static int N;
 
    static void mergesort(int l, int m, int r) {
        int i = l;
        int k = l;
        int j = m + 1;
 
        while (i <= m && j <= r) {
            if (list[i][0] > list[j][0]) {
                sorted[k][0] = list[i][0];
                sorted[k][1] = list[i][1];
 
                i++;
                k++;
            } else {
                sorted[k][0] = list[j][0];
                sorted[k][1] = list[j][1];
 
                rank[list[j][1]] -= (j - k);
 
                j++;
                k++;
            }
        }
 
        if (i > m) {
            for (; j <= r; j++, k++) {
                sorted[k][0] = list[j][0];
                sorted[k][1] = list[j][1];
            }
        } else if (j > r) {
            for (; i <= m; i++, k++) {
                sorted[k][0] = list[i][0];
                sorted[k][1] = list[i][1];
            }
        }
 
        for (int t = l; t <= r; t++) {
            list[t][0] = sorted[t][0];
            list[t][1] = sorted[t][1];
        }
    }
 
    static void merge(int l, int r) {
        if (l != r) {
            int m = (l + r) / 2;
            merge(l, m);
            merge(m + 1, r);
            mergesort(l, m, r);
        }
    }
 
    static void print() {
        StringBuilder sb = new StringBuilder();
        
        for (int i = 1; i <= N; i++) {
            sb.append(rank[i]+"\n");
        }
        System.out.println(sb.toString());
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new int[N + 1][2];
        sorted = new int[N + 1][2];
        rank = new int[N + 1];
 
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            list[i][0] = Integer.parseInt(st.nextToken());
            list[i][1] = i;
            rank[i] = i;
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        merge(1, N);
        print();
    }
}

 

다음은 Segment Tree 방식입니다.

이 방식은 구간 합을 구하는 방식으로 해결할 수 있습니다.

먼저 list 배열을 실력의 오름차순으로 정렬한 후, 순서대로 인덱스를 트리에 저장해주시면 됩니다.

 

실력 순으로 query 후 update를 진행하기 때문에 query로 트리를 탐색할 때는 모든 값들이 자신보다 실력이 낮은 값들입니다.

여기서 인덱스가 자신보다 앞에 있는 갯수만 찾으시면 됩니다..

 

merge sort방식으로 구현

segment tree방식으로 구현

문제에 명시되어있는 풀이방법은 Segment Tree인데 Merge Sort방식으로 풀이한게 더 빠른 시간이 나왔습니다.

제가 로직을 잘못 구현했을 수도 있지만 여러방식으로 시도해봐야겠습니다..

 

 

[Segment Tree]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[][], tree[], rank[];
    static int N;
 
    static int query(int node, int s, int e, int l, int r) {
        if (l <= s && e <= r)
            return tree[node];
        if (s > r || e < l)
            return 0;
 
        int m = (s + e) / 2;
        return query(node * 2, s, m, l, r) + query(node * 2 + 1, m + 1, e, l, r);
    }
 
    static void update(int node, int s, int e, int idx) {
        if (idx < s || idx > e)
            return;
 
        tree[node]++;
        int m = (s + e) / 2;
        if (s != e) {
            update(node * 2, s, m, idx);
            update(node * 2 + 1, m + 1, e, idx);
        }
    }
 
    static void func() {
        StringBuffer sb = new StringBuffer();
        for (int i = 1; i <= N; i++) {
            int ans = query(1, 1, N, 1, list[i][1]);
 
            rank[list[i][1]] = list[i][1] - ans;
            update(1, 1, N, list[i][1]);
        }
 
        for (int i = 1; i <= N; i++) {
            sb.append(rank[i]+"\n");
        }
        System.out.println(sb.toString());
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new int[N + 1][2];
        rank = new int[N + 1];
        tree = new int[N * 4];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            list[i][0] = Integer.parseInt(st.nextToken());
            list[i][1] = i;
        }
 
        Arrays.sort(list, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                if (a[0] > b[0])
                    return 1;
                else
                    return -1;
            }
        });
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}