-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy paths2020_4.java
More file actions
105 lines (85 loc) · 2.46 KB
/
s2020_4.java
File metadata and controls
105 lines (85 loc) · 2.46 KB
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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
package org.codingTest;
import java.util.*;
public class s2020_4 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int length = sc.nextInt();
int count = sc.nextInt();
String str = sc.next();
List<Info> list = new ArrayList<>();
char alphabet = str.charAt(0);
int num = 0;
int start = 0;
for (int i = 0; i < length; i++) {S
System.out.print(str.charAt(i) + ", ");
if (alphabet != str.charAt(i)) {
list.add(new Info(alphabet, start, i - 1, num));
num = 1;
start = i;
alphabet = str.charAt(i);
} else {
num++;
}
}
list.add(new Info(str.charAt(length - 1), start, length - 1, num));
Collections.sort(list);
System.out.println();
System.out.println("size--->" + list.size());
for (int i = 0; i < list.size(); i++) {
Info info = list.get(i);
System.out.println(info.alphabet + " start:" + info.start + " end:" + info.end + " count:" + info.count);
}
while (count-- > 0) {
int s = sc.nextInt() - 1;
int e = sc.nextInt() - 1;
char startAlphabet = str.charAt(s);
char endAlphabet = str.charAt(e);
System.out.println("start alphabet:" + startAlphabet);
char answer = 'A';
int max = 0;
for (int i = 0; i < list.size(); i++) {
Info info = list.get(i);
if (info.start > e || info.end < s)
continue;
int cnt = info.count;
if (info.alphabet == startAlphabet)
cnt = info.end - s + 1;
else if (info.alphabet == endAlphabet)
cnt = e - info.start + 1;
if (info.alphabet == startAlphabet && info.alphabet == endAlphabet)
cnt = e - s + 1;
System.out
.println("alphabet:" + info.alphabet + " , cnt:" + cnt + " , answer=" + answer + " max:" + max);
if (max == cnt && answer - info.alphabet > 0) {
System.out.println("answer:" + answer + ", new alpa:" + info.alphabet);
answer = info.alphabet;
}
if (max < cnt) {
answer = info.alphabet;
max = cnt;
}
}
System.out.println(answer);
}
}
}
class Info implements Comparable<Info> {
char alphabet;
int start;
int end;
int count;
Info(char alphabet, int start, int end, int count) {
this.alphabet = alphabet;
this.start = start;
this.end = end;
this.count = count;
}
@Override
public int compareTo(Info info) {
if (this.count == info.count)
return this.alphabet - info.alphabet;
else {
return info.count - this.count;
}
}
}