[BOJ] 1764 - 듣보잡(Java)

문제

굉장히 단순했던 문제이다. 명단이 2개 주어지고, 동시에 명단에 포함되어있는 이름을 찾아야 한다. 알고리즘은 단순하지만, 어떤 자료구조에 값을 저장할지 선택을 잘 해야 시간초과가 뜨지 않는다

자료 구조, 해시를 사용한 집합과 맵, 정렬, 문자열

 

Approach 1 ❌

• 2개의 배열을 선언하고 N, M개의 이름을 각각 저장한다. 이후, 이중 for 루프로 중복되는 이름을 찾는다.
• 여기서 문제가 발생하였는데, 테스트케이스 출력에는 문제가 없으나 제출하고 나니 시간초과가 떴다. 코드를 살펴보니 시간복잡도를 고려하지 않아 최악의 경우엔 O(N * M)이므로 무려 2.5억번의 연산이 발생하게 된다.

 

Approach 2 ⭕

• 접근 방식을 수정하여 일반적인 배열 대신 HashSet과 ArrayList를 활용하였다.
• 중복된 이름을 찾을 때 HashSet은 해시기반으로 O(1) 시간에 탐색이 가능하여 매우 빠르다!
• 시간복잡도가 O(N + M)으로 감소하여 문제없이 제출이 되었다.

package org.example;

import java.util.*;
import java.io.*;

public class Main {
    static int N, M;

    static HashSet<String> set = new HashSet<>();
    static ArrayList<String> result = new ArrayList<>();

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

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

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

        Collections.sort(result);

        sb.append(result.size()).append("\n");
        for(String s : result){
            sb.append(s).append("\n");
        }

        System.out.println(sb);
    }
}

 

느낀 점 및 메모 💡

• 단순한 알고리즘이라도 자료구조 선택을 신중하게 해야겠다.
• 재밌었던 점은 ArrayList 클래스에 내장된 contains 함수는 시간초과를 유발한다는 것이었다. 같은 메서드여도 자료구조에 따라서 성능이 달라지므로 잘 숙지하여 활용해야겠다.

 

레퍼런스 📄

https://kau-algorithm.tistory.com/1014