백준 1764. 듣보잡

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

나의 풀이(시간 초과)

package test;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class test68 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		try {
			StringBuilder sb = new StringBuilder();
			int cnt = 0;
			StringTokenizer st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());
			ArrayList<String> al = new ArrayList<String>();
			while (n-- > 0) {
				String neverHeard = br.readLine();
				al.add(neverHeard);
			}
			Collections.sort(al);
			while (m-- > 0) {
				String neverSaw = br.readLine();
				if (al.contains(neverSaw)) {
					cnt++;
					sb.append(neverSaw);
					if (m > 1) {
						sb.append("\n");
					}
				}
			}
			String answer = String.valueOf(sb);
			bw.write(String.valueOf(cnt + "\n"));
			bw.write(answer);
			bw.flush();
			br.close();
			bw.close();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}

}

 

 

나의 두번째 풀이(O(n*m)의 시간복잡도를 해결하기 위해 map을 사용)

package test;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.StringTokenizer;

public class test68 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		try {
			StringBuilder sb = new StringBuilder();
			int cnt = 0;
			StringTokenizer st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());
			HashMap<String,String> hm = new HashMap<>();
			ArrayList<String> al = new ArrayList<String>();
			while (n-- > 0) {
				String neverHeard = br.readLine();
				hm.put(neverHeard, neverHeard);
			}

			while (m-- > 0) {
				String neverSaw = br.readLine();
				if (hm.get(neverSaw) != null) {
					cnt++;
					al.add(neverSaw);
				}
			}
			Collections.sort(al);
			for(int i = 0; i<al.size(); i++) {
				sb.append(al.get(i));
				if(i<al.size()-1) {
					sb.append("\n");					
				}
			}
			String answer = String.valueOf(sb);
			bw.write(String.valueOf(cnt + "\n"));
			bw.write(answer);
			bw.flush();
			br.close();
			bw.close();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}

}