[백준] 1764번 듣보잡!!!!!문제 hashmap문제

https://www.acmicpc.net/problem/1764문제이다.

입력받은 첫번째 배열에서 두번째 배열과 공통되는게 있는지 묻는 질문이다. 
편하게 배열로 받아서 처음부터 끝까지 검색하면 시간초과가 된다.

이럴 경우 hasmap을 이용해 문제를 풀자 

중요한점은 출력할떄 "사전순"으로 출력 해야한다. 이부분을 놓쳐서 처음 제출때 틀렷다 ㅜㅜ

 

출력값을 찾은 후 정렬하는것이 시간적으로 이득이 많겠지만 값을 찾기전에 사전순으로 출력값을 찾는 코드로 짜보았다.

import java.util.Scanner;
import java.util.HashMap;
import java.util.Collections;
import java.util.ArrayList;
public class Main {

	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		HashMap<String,Integer> map = new HashMap<>();
		int a = sc.nextInt();
		int b = sc.nextInt();
		int count = 0;
		for(int i=0;i<a;i++) {
			String n = sc.next();
			map.put(n,1);
		}
		ArrayList<String> list = new ArrayList<>();
		for(int i=0;i<b;i++) {
			list.add(sc.next());
		}
		Collections.sort(list);
		for(int i=0;i<b;i++) {
			if(map.containsKey(list.get(i))) {
				count++;
				sb.append(list.get(i)+"\n");
			}
		}
		
		System.out.println(count);
		System.out.println(sb);
	}
	
}

Collections.sort(list) 는 arraylist를 사전순으로 정렬해준다. 꼭 기억하자 

hashmap은 key와 value값으로 이루어져있다.

key값을 이용해 값을 찾는 것은 시간효율이 좋지만 그 반대는 O(N)의 시간이 걸리니 이점 유의해서 알고리즘을 풀자.