오늘 풀어본 문제는 ⭐숫자 카드2 라는 문제이다.
1. 문제 요약
- 정수가 적힌 숫자 카드가 있다.
- 상근이는 여러 장의 카드를 가지고 있다. (같은 숫자의 카드가 여러 장 있을 수 있음)
- 특정 숫자가 적힌 카드를 몇 장 가지고 있는지 구하는 문제이다.
2. 입출력
입력
① 상근이가 가진 카드 정보
- 카드 개수
N(1 ≤ N ≤ 500,000) - 각 카드에 적힌 정수
(-10,000,000 ≤ 숫자 ≤ 10,000,000)
② 확인해야 할 카드 정보
- 알고 싶은 카드 개수
M - 확인할 카드에 적힌 정수
(-10,000,000 ≤ 숫자 ≤ 10,000,000)
출력
- 입력으로 주어진 각 숫자 카드에 대해
상근이가 몇 장 가지고 있는지 공백으로 구분하여 출력한다.
3. 첫 번째 구현 방법
접근 방식
- 카드 배열을 정렬한다.
- 이분 탐색으로 특정 숫자를 찾는다.
- 찾은 위치에서 왼쪽/오른쪽으로 확장하며 같은 숫자의 개수를 센다.
문제점
이 방식은 최악의 경우 시간 초과가 발생할 수 있다.
이분 탐색 자체는 O(log N)이지만,
- 같은 숫자가 많을 경우 왼쪽으로 최대
N/2 - 오른쪽으로 최대
N/2
까지 탐색해야 한다.
즉, 한 번의 질의에 최대 O(N)이 걸릴 수 있다.
만약 카드의 개수가 최대치라면?
- 카드 하나를 찾는 데 걸리는 최악 시간:
O(N) - 질의가 M개일 때:
O(N × M)
N, M이 최대 500,000일 경우
500,000 × 500,000 = 250,000,000,000
사실상 O(N²) 수준이 되어 시간 초과가 발생한다.
4. 정답 구현 방법
핵심 아이디어
정렬된 배열에서 특정 값 x의 개수는 다음처럼 구할 수 있다.
lower_bound(x): x가 처음 등장하는 위치upper_bound(x): x보다 큰 값이 처음 등장하는 위치
따라서 x의 등장 횟수는
count(x) = upper_bound(x) - lower_bound(x)
이분탐색 upper bound / lower bound 찾기
둘 다 구조가 동일하다. 하지만 lower의 경우, 찾는 범위가 =에 포함되어야 하고, upper은 포함되지 않는다는 것이 다르다.
[lower bound]
: lower의 경우, 현재 타겟과 같은 값을 찾았다면 그건 정답일 가능성이 있다.
=> 그렇기에 인덱스를 옮기지 않고 hi만 내린다.
int lo = 0;
int hi = N;
while( lo < hi ) {
int mid = (lo + hi) / 2;
if ( value [mid] <= target )
hi = mid;
else
lo = mid + 1;
}
return lo;[upper bound]
: upper의 경우, 현재 값이 찾는 값과 같다면, 범위에서 벗어나는 것이다.
(upper은 찾는 수가 처음으로 초과되는 인덱스를 찾는다.)
=> 그렇기에 같은 경우는 밑의 케이스은 mid + 1을 통해 lo를 올린다.
int lo = 0;
int hi = N;
while( lo < hi ) {
int mid = (lo + hi) / 2;
if ( value [mid] < target )
hi = mid;
else
lo = mid + 1;
}
return lo;
5. 정답 코드
import java.io.*;
import java.util.*;
public class Main {
static int N;
static int[] number;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
number = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
number[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(number);
int M = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
for (int i = 0; i < M; i++) {
int x = Integer.parseInt(st.nextToken());
sb.append(upperBound(x) - lowerBound(x));
if (i < M - 1) {
sb.append(" ");
}
}
System.out.println(sb.toString());
}
static int lowerBound(int target) {
int lo = 0;
int hi = N;
while (lo < hi) {
int mid = (hi + lo) / 2;
if (number[mid] >= target) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
static int upperBound(int target) {
int lo = 0;
int hi = N;
while (lo < hi) {
int mid = (hi + lo) / 2;
if (number[mid] > target) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
}