문제
N개의 숫자 카드를 가진 상근이에게 M개의 숫자를 하나씩 물어볼 때, 해당 숫자 카드를 몇 개 가지고 있는지 출력하는 문제다. 카드 숫자 범위는 -10,000,000 ~ 10,000,000이다.
입력
- 첫째 줄: N
- 둘째 줄: N개의 카드 숫자
- 셋째 줄: M
- 넷째 줄: M개의 질의 숫자
출력
각 질의 숫자에 해당하는 카드 개수 (공백 구분)
예제
| 입력 | 출력 |
|---|---|
10 6 3 2 10 10 10 -10 -10 7 3 8 10 9 -5 2 3 4 5 -10 | 3 0 0 1 2 0 0 2 |
풀이
10815번(숫자 카드)의 확장 문제로, 존재 여부(0/1) 대신 개수를 반환한다. 동일하게 카운팅 배열을 활용해 O(N+M)으로 해결한다.
- 크기 20,000,001의
cnt배열을 선언한다. 오프셋은 10,000,000이다. - N개의 카드를 읽으며
cnt[10_000_000 + 카드값]++해 빈도를 누적한다. - M개의 질의를 읽으며
cnt[10_000_000 + 질의값]의 값을 그대로 출력한다.
핵심 아이디어: 10815와 동일한 카운팅 배열 접근법이지만, 단순 0/1 판단 대신 누적된 빈도값을 직접 읽는다. 범위가 고정되어 있어 이분 탐색 없이 O(N+M)에 처리 가능하다.
코드
package com.ssafy.an.day049;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day07BOJ10816숫자카드2 { // 10816번 숫자 카드2
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st = null;
int N = Integer.parseInt(br.readLine()); // N개의 카드를 가지고 있음
int[] cnt = new int[20_000_001];
st = new StringTokenizer(br.readLine());
for (int n = 0; n < N; n++) {
cnt[10_000_000 + Integer.parseInt(st.nextToken())]++;
}
int M = Integer.parseInt(br.readLine()); // M개의 순서대로 몇개 가지고 있는 지
st = new StringTokenizer(br.readLine());
for (int m = 0; m < M; m++) {
int num = cnt[10_000_000 + Integer.parseInt(st.nextToken())];
sb.append(num+" ");
}
System.out.println(sb);
br.close();
}
}복잡도
- 시간: O(N + M)
- 공간: O(V) — V = 값의 범위 (20,000,001)