[BOJ] 1764. 듣보잡
https://www.acmicpc.net/problem/1764
문제
김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다.
듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.
출력
듣보잡의 수와 그 명단을 사전순으로 출력한다.
풀이
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
HashSet<String> listen = new HashSet<String>();
ArrayList<String> listenHear = new ArrayList<>();
for (int i = 0; i < n; i++) {
listen.add(br.readLine());
}
while (m-- > 0) {
String s = br.readLine();
if (listen.contains(s))
listenHear.add(s);
}
listenHear.sort((s1, s2) -> (s1).compareTo(s2));
bw.write(listenHear.size()+"\n");
for (String name : listenHear) {
bw.write(name+"\n");
}
bw.flush();
bw.close();
}
}
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
HashSet<String> listen = new HashSet<String>();
ArrayList<String> listenHear = new ArrayList<>();
for (int i = 0; i < n; i++) {
listen.add(br.readLine());
}
while (m-- > 0) {
String s = br.readLine();
if (listen.contains(s))
listenHear.add(s);
}
listenHear.sort((s1, s2) -> (s1).compareTo(s2));
bw.write(listenHear.size()+"\n");
for (String name : listenHear) {
bw.write(name+"\n");
}
bw.flush();
bw.close();
}
}
처음에는 ArrayList로 풀었다가 시간초과가 나서 찾아보니
HashSet을 사용해야 풀 수 있는 문제였다.
HashSet의 contains()는 map을 기반으로 구현되어 O(1), ArrayList의 contains()는 indexOf()를 사용하기에 O(n)의 시간복잡도를 가진다!
포함여부를 묻는 문제에선 ArrayList보단 HashSet을 사용해야 한다는 깨달음을 얻은 문제였다.
또 Hash 문제를 여러개 풀어보며, HashSet과 HashMap의 차이도 알게 되었다.
[부록] HashSet과 HashMap의 차이
- HashSet : 해시 메커니즘을 사용하여 요소를 저장.
성공적으로 추가되면 true를, 중복된 객체가 들어오면 false를 리턴
HashMap에 비해 느림- HashMap : key-value 형식의 데이터 저장. 중복 객체 마찬가지로 안받음
unique key를 이용하여 데이터에 바로 접근하므로 HashSet에 비해서 빠름
Author And Source
이 문제에 관하여([BOJ] 1764. 듣보잡), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yoon_0/BOJ-1764.-듣보잡저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)