[백준] S4 1764번 듣보잡 (Java)

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

👉 문제

듣도 못한 사람의 수 N에 따른 사람의 이름을 ArrayList에 넣은 후, 보도 못한 사람의 수 M 만큼의 사람의 이름이 contains하는지 검사하여 다시 ArrayList에 넣어 출력하려고 했다. 하지만 역시나 시간초과... (이 코드는 넣지 않도록 하겠다.) 아마 N,M이 500,000이하의 자연수라고 하니 최대의 경우엔 너무 오래걸리는게 아닐까 싶다.

하여 ArrayList를 HashSet으로 바꾸면 왠지 바로 될거 같아 해보니 바로 맞췄고 생각보다 시간이 엄청 짧게 걸렸다. 역시 얼른 자료구조를 공부해서 적재적소에 사용할 수 있어야 할텐데 😢

근데 더 엄청난 것은 이후 다른 사람의 채점현황을 뒤져보다가 유독 코드 길이가 짧은 코드를 보게되었는데, 이런식의 풀이는 또 처음본다. stream()을 이용하는 풀이인데, ...

👉 풀이

1. 듣도 못한 사람의 수 N에 따른 사람의 이름을 HashSet에 넣은 후, 보도 못한 사람의 수 M 만큼의 사람의 이름이 contains하는지 검사하여 ArrayList에 넣어 사전순으로 정렬 후 출력

package Baekjoon;

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 _1764_1 {
    public static void main(String[] args) throws Exception {
        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> people = new HashSet<>();
        ArrayList<String> noHearSee = new ArrayList<>();

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

        for (int i = 0; i < M; i++) {
            String noSee = br.readLine();
            if (people.contains(noSee)) {
                noHearSee.add(noSee);
            }
        }
        Collections.sort(noHearSee);

        StringBuilder sb = new StringBuilder();

        sb.append(noHearSee.size()).append('\n');
        for (String s : noHearSee) {
            sb.append(s).append('\n');
        }

        System.out.print(sb);
    }
}

2. stream()을 이용한 방식

package Baekjoon;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class _1764_2 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] nm = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt).toArray();

        Set<String> set1 = new HashSet<>();
        Set<String> set2 = new HashSet<>();

        for (int i = 0; i < nm[0]; i++) set1.add(br.readLine());
        for (int i = 0; i < nm[1]; i++) set2.add(br.readLine());
        set1.retainAll(set2);

        System.out.println(set1.size());
        set1.stream().sorted().forEach(System.out::println);
    }
}

👉 성능

채점번호 : 69946900 - 방법 2 : stream()을 이용한 방식
채점번호 : 69946482 - 방법 1 : HashSet, ArrayList 이용

자바에서 람다와 스트림에 대해 공부한 적이 없어서 잘 모르지만 찾아볼까 하다가 우선 자바의 정석 공부하고 있던 것의 진도를 빨리 나가야겠다 싶었다