https://www.acmicpc.net/problem/2517
2517번: 달리기
첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는
www.acmicpc.net
자신 앞에 있는 사람들 중 자신보다 실력이 더 낮은 사람이 몇 명인지 구하는 문제입니다.
이 문제는 두 가지 방법으로 해결하였습니다.
예전에 배운적 있었던 Merge Sort방법과 이 문제의 풀이방법으로 명시되어 있는 Segment Tree 방법으로 문제를 두번 풀어보았습니다.
먼저 Merge Sort 방법입니다.
평소의 Merge Sort를 사용했던 것처럼 i번과 j번을 서로 비교해가며 큰 값을 sorted[k]에 저장하는 방식입니다.
여기서 기존의 Merge Sort에 추가해야 할 것이 하나 있는데
i번은 앞의 인덱스, j번은 뒤의 인덱스 이므로 j번 인덱스의 값이 앞으로 이동하게 되면 그 차이만큼 rank에서 빼줍니다. (i번이 뒤로가는 것은 무시하셔도 됩니다.)
작년에 C++로 동일한 방식으로 해결하였으나 java에서는 TLE를 받았는데
아는 형님께서 StringBuilder라는 것을 알려주셨고, 출력 부분에 이것만 추가하니 AC를 받았습니다.
StringBuilder를 이제 자주 써야겠다는 생각이 드는군요 ㅎㅎ
오늘도 하나 배워갑니다..
[Merge Sort]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
|
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();
}
}
|
cs |
다음은 Segment Tree 방식입니다.
이 방식은 구간 합을 구하는 방식으로 해결할 수 있습니다.
먼저 list 배열을 실력의 오름차순으로 정렬한 후, 순서대로 인덱스를 트리에 저장해주시면 됩니다.
실력 순으로 query 후 update를 진행하기 때문에 query로 트리를 탐색할 때는 모든 값들이 자신보다 실력이 낮은 값들입니다.
여기서 인덱스가 자신보다 앞에 있는 갯수만 찾으시면 됩니다..
문제에 명시되어있는 풀이방법은 Segment Tree인데 Merge Sort방식으로 풀이한게 더 빠른 시간이 나왔습니다.
제가 로직을 잘못 구현했을 수도 있지만 여러방식으로 시도해봐야겠습니다..
[Segment Tree]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
|
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();
}
}
|
cs |
'algorithm > data-structure' 카테고리의 다른 글
| boj 5639 이진 검색 트리 (0) | 2021.01.24 |
|---|---|
| boj 1991 트리 순회 (0) | 2021.01.22 |
| boj 11003 최솟값 찾기 (0) | 2021.01.22 |
| boj 1517 버블 소트 (0) | 2021.01.22 |
| boj 3425 고스택 (0) | 2021.01.22 |