[백준] S4 4158번 CD (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

4158번: CD

[문제] 

상근이와 선영이는 동시에 가지고 있는 CD를 팔려고 한다. CD를 몇 개나 팔 수 있을까?

[입력]

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 상근이가 가지고 있는 CD의 수 N, 선영이가 가지고 있는 CD의 수 M이 주어진다. N과 M은 최대 백만이다. 다음 줄부터 N개 줄에는 상근이가 가지고 있는 CD의 번호가 오름차순으로 주어진다. 다음 M개 줄에는 선영이가 가지고 있는 CD의 번호가 오름차순으로 주어진다. CD의 번호는 십억을 넘지 않는 양의 정수이다. 입력의 마지막 줄에는 0 0이 주어진다.

상근이와 선영이가 같은 CD를 여러장 가지고 있는 경우는 없다.

[출력]

두 사람이 동시에 가지고 있는 CD의 개수를 출력한다.

 

 

---

[풀이]

1. 중복이 된 것의 개수를 세주면 된다.

2. 시간이 1초기 때문에 들어올 수 있는 100만 개를 100만 번 비교하면 시간 초과가 발생한 거라고 생각하고 속도가 빠른 HashSet을 사용하였다.

3. 상근이가 가진 CD를 해쉬셋에 담아준다.

4. 선영이가 가진 CD가 해쉬셋에 포함되어 있다면 count를 증가해준다.

[접근]

1. 100만개씩 받을 수 있는데 100만 * 100만이 되면 1초를 벗어난다.

2. 시간 속도가 빠른 HashSet을 사용해줬다.

3. 해쉬셋의 contains를 이용해 이미 포함이 되어있는지 판단하였다.

4. 있다면 count를 증가시키고 마지막에 이 count를 출력시킨다.

[코드]

package BOJ_silver;

import java.util.*;
import java.io.*;

public class Main_S4_4158_김재욱 {
	static int n;
	static int m;
	static HashSet<Integer> set;
	static int count;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		while (true) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());

			// 0, 0 이 들어오면 종료
			if (n == 0 && m == 0) {
				break;
			}
			
			// 초기화
			set = new HashSet<>();
			count = 0;
			
			// 상근이가 가진 cd를 셋에 담기
			for (int i = 0; i < n; i++) {
				set.add(Integer.parseInt(br.readLine()));
			}
			
			// 선영이가 가진 cd가 셋에 있는지 확인
			for (int j = 0; j < n; j++) {
				int cd = Integer.parseInt(br.readLine());
				
				// 이미 있다면
				if (set.contains(cd))
					count++; // 공통으로 가지고 있는 것이니까 count 증가
			}
			
			System.out.println(count);
		}
	}
}