문제
두 사람이 소유한 CD 목록이 오름차순으로 주어질 때, 둘 다 가지고 있는 CD의 수를 구하라.
입력
여러 테스트 케이스가 주어진다. 각 케이스의 첫 줄에 N, M, 이후 N개와 M개의 CD 번호가 오름차순으로 주어진다. 0 0이면 종료.
출력
각 테스트 케이스마다 공통 CD의 수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 3 1 2 3 1 2 4 0 0 | 2 |
풀이
두 배열이 정렬되어 있으므로 투 포인터로 교집합의 크기를 구한다.
- 두 포인터 i, j를 각각 0부터 시작한다
- 두 값이 같으면 공통 CD이므로 카운트 증가 후 양쪽 포인터를 전진한다
- 한쪽이 더 크면 작은 쪽의 포인터를 전진한다
- 어느 한쪽이 끝나면 종료한다
핵심 아이디어: 정렬된 두 배열의 교집합 크기를 투 포인터로 O(N+M)에 구할 수 있다.
코드
package day749;
import java.io.*;
import java.util.*;
public class Day705BOJ4158CD {
static int N, M, ans;
static int[] arrN, arrM;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
while (true) {
st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
if (N == 0 && M == 0) {
break;
}
arrN = new int[N];
for (int i = 0; i < N; i++) {
arrN[i] = Integer.parseInt(br.readLine());
}
arrM = new int[M];
for (int i = 0; i < N; i++) {
arrM[i] = Integer.parseInt(br.readLine());
}
ans = 0;
int i = 0, j = 0;
while (i < N && j < M) {
if (arrN[i] == arrM[j]) {
ans++;
i++;
j++;
} else if (arrN[i] > arrM[j]) {
j++;
} else {
i++;
}
}
sb.append(ans + "\n");
}
System.out.println(sb);
}
}복잡도
- 시간: O(N+M)
- 공간: O(N+M)