[백준_1764번] 듣보잡

 

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

1764번: 듣보잡

[문제]

 김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.

 

[입력 조건]

 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 영어 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다.

 

[코드]

import java.util.*;

public class BaekJoon_1764 {
	public static HashSet<String> hs=new HashSet<>();
	public static ArrayList<String> result=new ArrayList<>();
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int m=sc.nextInt();
		
		// 듣도 못한 사람 HashSet에 저장
		for(int i=0;i<n;i++)
			hs.add(sc.next());
		
		// 보도 못한 사람 중 듣도 못한 사람과 같은 있다면 연결리스트에 저장
		for(int i=0;i<m;i++) {
			String str=sc.next();
			if(hs.contains(str))
				result.add(str);
		}
		
		Collections.sort(result); // 정렬
		
		System.out.println(result.size()); // 듣도 보도 못한 사람 수 출력
		// 듣도 보도 못한 사람 이름 출력
		for(int i=0;i<result.size();i++)
			System.out.println(result.get(i));
	}

}

 

[고찰]

 처음에는 각 그룹의 명단을 배열에 저장하고, 2중 for문을 사용하여 완전 탐색으로 풀었지만 시간초과로 인해 방법을 바꿔야 했다. 그 방법은 중복을 허용하지 않고, contains() 함수를 사용하여 해당 문자열이 자료구조 내에 포함되어 있는지 확인할 수 있는 HashSet을 사용하여 시간초과 없이 문제를 해결할 수 있었다. 또한 2중 for문이 아닌 두 번째 그룹을 입력 받을 때 입력받은 값이 HashSet에 포함되어 있는지 바로 확인하면 모든 과정은 하나의 for문으로 해결할 수 있다.