문제
N개의 숫자 카드를 가진 상근이에게 M개의 숫자를 하나씩 물어볼 때, 해당 숫자 카드를 가지고 있으면 1, 없으면 0을 출력하는 문제다. 카드 숫자 범위는 -10,000,000 ~ 10,000,000이다.
입력
- 첫째 줄: N
- 둘째 줄: N개의 카드 숫자
- 셋째 줄: M
- 넷째 줄: M개의 질의 숫자
출력
각 질의에 대해 0 또는 1 (공백 구분)
예제
| 입력 | 출력 |
|---|---|
5 6 3 2 10 -10 8 10 9 -5 2 3 4 5 -10 | 1 0 0 1 1 0 0 1 |
풀이
카드 숫자 범위가 -10,000,000 ~ 10,000,000으로 정해져 있으므로, 크기 20,000,001짜리 배열을 직접 인덱싱 테이블로 활용한다. 오프셋 10,000,000을 더해 음수 인덱스 문제를 해결한다.
- 크기 20,000,001의
cnt배열을 선언한다. 오프셋은 10,000,000이다. - N개의 카드를 읽으며
cnt[10_000_000 + 카드값]++한다. - M개의 질의를 읽으며
cnt[10_000_000 + 질의값] > 0이면 1, 아니면 0을 출력한다.
핵심 아이디어: 값 범위가 고정된 경우 배열을 해시 테이블처럼 사용하면 O(1) 조회가 가능하다. 이분 탐색(O(N log N)) 대신 카운팅 배열(O(N))로 더 빠르게 풀었다. 복잡도는 O(N+M)이다.
코드
package com.ssafy.an.day049;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day07BOJ10815숫자카드 { // 10815번 숫자 카드
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++) {
if (0 < cnt[10_000_000 + Integer.parseInt(st.nextToken())]) {
sb.append(1 + " ");
} else {
sb.append(0 + " ");
}
}
System.out.println(sb);
br.close();
}
}복잡도
- 시간: O(N + M)
- 공간: O(V) — V = 값의 범위 (20,000,001)