백준 1764 <듣보잡>

1764번: 듣보잡 (acmicpc.net)

1764번: 듣보잡

중복을 다루는 문제이다.

주어진 두번의 문자열들의 집합에서 , 중복되는걸 찾아서 사전순으로 return하라는 문제다.

중복을 다루니까 map을 활용하면 편하겠고 사전순으로 return.. > sort해야겠다는 생각

n.m의 max가 50만이니, 정렬할때 nlogn짜리 sort()메소드 활용.

이 정도의 아이디어만 있으면 쉽게 풀리겠다 !

 

추가적인 tip이지만 Map.containsKey()의 시간복잡도는 평균적으로  O(1)이니, 1중for문과 엮을때 편리하겠다.

package 백준;
import java.util.*;



import java.io.*;
public class _1764_듣보잡 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int neverlisten = Integer.parseInt(st.nextToken());
		int neverheard = Integer.parseInt(st.nextToken());
		
		HashMap<String,Integer> hs = new HashMap<String,Integer>();
		String[] neverlistenppl = new String[neverlisten];
		String[] neverheardppl = new String[neverheard];
		for(int i=0; i<neverlisten; i++) {
			neverlistenppl[i] = br.readLine();
		}
		for(int i=0; i<neverheard; i++) {
			neverheardppl[i] = br.readLine();
		}
		
		for(int i=0; i<neverlisten; i++) {
			if(hs.containsKey(neverlistenppl[i])) {
				hs.put(neverlistenppl[i], hs.get(neverlistenppl[i])+1);
			}
			else {
				hs.put(neverlistenppl[i], 1);
			}
		}
		
		for(int i=0; i<neverheard; i++) {
			if(hs.containsKey(neverheardppl[i])) {
				hs.put(neverheardppl[i], hs.get(neverheardppl[i])+1);
			}
			else {
				hs.put(neverheardppl[i], 1);
			}
		}
		
		ArrayList<String> al = new ArrayList<String>();
		
		
		for(Map.Entry<String, Integer> entry : hs.entrySet()) {
			if(entry.getValue() >1) {
				al.add(entry.getKey());
			}
		}
		
		Collections.sort(al);
		StringBuilder sb = new StringBuilder();
		
		sb.append(al.size()).append('\n');
		for(int i=0; i<al.size(); i++) {
			sb.append(al.get(i)).append('\n');
		}
		
		
		System.out.println(sb);
		
		
		
		
		
	}

}