[백준] 1764번: 듣보잡(구현, 정렬) - HashSet

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

1764번: 듣보잡

틀린 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		String[] nArr = new String[N];	// 듣도 못한 사람 저장
		String[] mArr = new String[M];	// 보도 못한 사람 저장
		String[] nmArr = new String[500000];	// 듣도 보도 못한 사람 저장
		int index = 0;
		int count = 0;
		
		// 듣도 못한 사람 입력
		for(int i=0; i<nArr.length; i++) 
			nArr[i] = bf.readLine();
		// 보도 못한 사람 입력
		for(int i=0; i<mArr.length; i++)
			mArr[i] = bf.readLine();
		
		Arrays.sort(nArr);
		Arrays.sort(mArr);
		
//		for(int i=0; i<N; i++)
//			System.out.print(nArr[i] + " ");
//		System.out.println();
//		for(int i=0; i<M; i++)
//			System.out.print(mArr[i] + " ");
		
		for(int i=0; i<nArr.length; i++) {
			for(int j=0; j<mArr.length; j++) {
				if(nArr[i].equals(mArr[j])) {	// 듣도 보도 못했을때 => 카운트 +1 , 저장
					count ++;
					nmArr[index ++] = nArr[i];
					break;
				}
			}
		}
		
		
		
		System.out.println(count);
		for(int i=0; i<nmArr.length; i++) {
			if(nmArr[i] == null)	break;
			System.out.println(nmArr[i]);
		}
		bf.close();
	}

}

풀이

가장 무난하게 듣도 못한 사람의 명단 - String nArr[] , 보도 못한 사람의 명단 - String mArr[] 배열을 선언하고,

듣도 보도 못한 사람의 명단을 저장하기 위해 String nmArr[] 을 선언했다.

그 후 각 배열에 완전탐색을 통해 2중 for문을 돌렸으나 시간초과가 발생했다.

사실 문제에서 N, M의 범위는 500,000 이어서 완전탐색으로 접근하기 전에 시간초과가 발생할거라고 생각은 했었지만 직접 구현하니 시간초과가 발생했다.

두 String 중 한 String이 포함되는지 안되는지 어떻게 해결해야 할 지 고민했지만 떠오르지 않았다.

다른 자료구조로 접근해야 할 것 같지만 자료구조가 아직 부족하여 다른 풀이를 참고했다.

정답 코드

import java.util.List;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int N = Integer.parseInt(st.nextToken());	// 듣도 못한 사람의 수
		int M = Integer.parseInt(st.nextToken());	// 보도 못한 사람의 수
		
		Set<String> hs = new HashSet<String>();	// 듣도 못한 사람 저장
		List<String> list = new ArrayList<String>();
		for(int i=0; i<N; i++)	
			hs.add(bf.readLine());	// 듣도 못한 사람 저장
		
		for(int i=0; i<M; i++) {
			String str = bf.readLine();
			// 보도 못한 사람이 듣도 못한 사람에 있을경우 => list에 저장
			if(hs.contains(str)) 	list.add(str);
		}
		
		Collections.sort(list);
		System.out.println(list.size());	// 듣도 보도 못한 사람의 수 => list의 크기
		for(int i=0; i<list.size(); i++)
			System.out.println(list.get(i));
		
		bf.close();
	}

}

풀이

HastSet을 이용해 듣도 못한 사람의 집단에 보도 못한 사람이 포함되는지 아닌지 판단할 수 있다.

 - HasbSet.contains() 

정답은 List에 담아서 저장한다.

 

듣도 못한 사람을 입력받고 HashSet에 저장한다. => hs.add()

그 후 보도 못한 사람을 입력받을 때 마다, 듣도 못한 사람을 저장한 HashSet에 있는경우 List에 저장한다.

최종적으로 명단을 사전순으로 출력하므로, List를 정렬하고 듣보잡의 수는 리스트의 크기인 size()가 된다.

 

위 알고리즘으로 구현하면 시간복잡도가 현저히 줄어든다.

이전 시간초과 코드에는 O(500,000 * 500,000) 였다면 위는 for문이 1개이므로 O(M)으로 구현할 수 있다.

 

 * 다양한 자료구조에 대해 더 익숙해져야할 것 같고, 시간복잡도에 대해 좀 더 생각할 수 있었다.