[백준] [자바/JAVA] 1764번 듣보잡

 

https://www.acmicpc.net/problem/1764

1764번: 듣보잡

 

 

 

 

 

---

 

 

 

 

 

 

 

 

문제

듣도 못한 사람의 명단과 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단. 듣보잡 구하기

 

즉 N만큼의 듣도 못한 사람의 명단,M만큼의 보도 못한 사람의 명단에서 중복된 사람의 수와 그 사람들을 사전순으로 출력하는 것이다.

 

 

 

 

 

---

 

 

 

 

 

문제풀이

사실 처음에는 듣도 못한 사람들과 보도 못한 사람들을 각각 ArrayList에 담고 각각 반복문을 돌면서 TreeSet으로 만든 듣보잡에 add 해주었다. 결과는 당연 실패

 

문제점

1. 듣도 못한 사람들과 보도 못한 사람들을 각각 따로 입력받고 또 각각 반복문을 돌면서 비교함.

2. ArrayList의 탐색성능이 우수할 것이라고 생각함.

 

해결방안

1. 듣도 못한 사람들을 입력받고, 보도 못한 사람들을 입력받을 때 듣도 못한 사람들과 비교를 해서 바로 듣보잡에 추가해주면 코드도 더 간결해지고, 굳이 각각 반복문을 수행하지 않아도 됨.

2. 반복문을 돌며 인덱스로 ArrayList를 탐색하면 빠를 것이라고 생각했지만, O(1)의 시간복잡도를 가지는 HashMap에는 한참 미치지 못하여 ArrayList에서 HashMap로 변경.

 

실버 4 난이도의 쉬운 문제였지만 자료구조 공부를 더 열심히 하라는 피드백을 준 문제였다

 

 

 

 

 

---

 

 

 

 

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {
	public static void main(String[] args) {
		try {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			String input = br.readLine();
			StringTokenizer st = new StringTokenizer(input);
			
			int n = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());
			
			Map<String, Boolean> notHearList = new HashMap<String, Boolean>();
			Set<String> notHearSeeList = new TreeSet<String>();
			
			for(int i=0; i<n; i++) {
				notHearList.put(br.readLine(), true);
			}
			for(int i=0; i<m; i++) {
				String key = br.readLine();
				if(notHearList.getOrDefault(key, false)) {
					notHearSeeList.add(key);
				}
			}
			
			System.out.println(notHearSeeList.size());
			for(String s : notHearSeeList)
				System.out.println(s);
			
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}