[백준 알고리즘] 1764번 : 듣보잡 (JAVA) 문제 풀이

문제

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

입력

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

듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.

출력

듣보잡의 수와 그 명단을 사전순으로 출력한다.

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

17609번: 회문

 

어떻게 풀 것인가?

처음에는 이중 For문으로 풀었다.

다만 조건을 꼼꼼히 살피지 못해서 시간 초과가 떳고, 이에 나는 자료구조에 눈을 돌렸다.

이에 나는 HashSet으로 우선 듣도못한 문자열을 입력받아서

이후에 보지도 못한 문자들을 입력받음 과 동시에 HashSet.contains 함수로 비교하고 존재한다면

strList에 집어 넣는다.

 

시간복잡도

시간 복잡도는 HashSet탐색이기에 O(1)이라는 시간복잡도가 존재한다.

 

공간복잡도

공간 복잡도의 경우 HashSet에 얼마나 많은 데이터가 들어가느냐가 관건이기에 O(N)이다.

 

풀면서 놓쳤던점

자료구조에 대한 이해가 아직도 부족한것 같다.

시간복잡도가 2초가 주어짐에 따라 넉넉하다고 생각을 하였고, 자료구조에 대한 생각을 전혀 하지 못했다.

 

이 문제를 통해 얻어갈 것

HashSet이라는 자바 자료구조에 대해서 공부를 진행하였다.

 

내 코드

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

public class Main {
	// 백준알고리즘 1764번 듣보잡

	static int N;
	static int M;

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		HashSet<String> set = new HashSet<>();

		ArrayList<String> strList = new ArrayList<String>();

		for (int i = 0; i < N; i++) {
			set.add(br.readLine());
		}

		for (int i = 0; i < M; i++) {
			String str = br.readLine();
			if (set.contains(str)) {
				strList.add(str);
			}

		}

		Collections.sort(strList);

		System.out.println(strList.size());

		for (String s : strList) {
			System.out.println(s);
		}
	}

}