문제 : boj11663
필요 알고리즘 개념
- 정렬, 해시, 이분 탐색, 누적합
- 이분 탐색을 활용하는 문제이다. 내 경우엔 prefix sum 개념도 좀 들어갔다.
※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.
풀이
[a, b] 이내에 포함된 점을 알려면 '[0, b]에 포함된 점의 개수 - [0, a-1]에 포함된 점의 개수' 를 구하면 될 것이다. (누적합 알고리즘 개념)
그럼 임의의 x에 대해 [0, x]에 포함된 점의 개수를 어떻게 구할 수 있을까? N개의 입력값을 정렬한 후, 작은 값부터 1개씩 더해진다고 생각하면 된다. 즉 예제 입력 1의 경우 아래와 같다. 이하의 값에 대해 x를 key로, [0,x]내의 점의 수를 value로 하는 HashMap으로 기록해두면 x만 구하면 O(1)로 범위 내의 점의 수를 알 수 있다.
그럼 이제 입력으로 a와 b가 주어졌을 때, [0,b]의 점의 수와 [0,a-1]의 점의 수만 구하면 된다. 그럴려면 a보다 작은 것 중 가장 큰 x의 값과, b보다 작거나 같은 것 중 가장 큰 x값을 찾을 수 있으면 된다. 이걸 이분 탐색으로 찾으면 될 것이다. 자바의 경우 TreeSet을 사용하면 이분 탐색을 쉽게 구현할 수 있다.
코드 : github
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;
import java.util.TreeSet;
public class Main {
private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<13);
public static void main(String[] args) throws Exception {
new Main().solution();
}
public void solution() throws Exception {
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int[] arr = new int[n];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
TreeSet<Integer> ts = new TreeSet<>();
HashMap<Integer, Integer> hs = new HashMap<>();
int cnt = 0;
for (int i = 0; i < n; i++) {
hs.put(arr[i], ++cnt);
ts.add(arr[i]);
}
StringBuilder sb = new StringBuilder();
while (m-->0) {
st = new StringTokenizer(br.readLine());
Integer a = Integer.parseInt(st.nextToken());
Integer b = Integer.parseInt(st.nextToken());
a = ts.lower(a);
b = ts.floor(b);
a = a==null? 0 : hs.get(a);
b = b==null? 0 : hs.get(b);
sb.append(b-a).append('\n');
}
System.out.print(sb);
}
}
'PS > BOJ' 카테고리의 다른 글
[자바] 백준 8783 - Architektura niezależna (java) (0) | 2023.01.10 |
---|---|
[자바] 백준 2571 - 색종이 - 3 (java) (0) | 2023.01.10 |
[자바] 백준 14927 - 전구 끄기 (java) (0) | 2023.01.06 |
[자바] 백준 9024 - 두 수의 합 (java) (0) | 2023.01.04 |
[자바] 백준 2843 - 마블 (java) (0) | 2023.01.02 |
댓글