듣보잡 - java

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ1764 {
    /**
     * 
     * @param noHearArr : 듣지도 못한 String형 배열
     * @param noSeeArr : 보지도 못한 String형 배열
     * @return : 듣도 보도 못한 String형 배열
     */
    static String[] solution(String[] noHearArr, String[] noSeeArr) {

        // 1. 정답을 담을 ArrayList생성
        List<String> answerList = new ArrayList<>();

        // HashSet 객체 생성
        HashSet<String> set = new HashSet<>();

        // for문 돌며 set에 noHear을 담아줌
        for(String noHear : noHearArr){
            set.add(noHear);
        }

        // for문 돌며 noSeeArr을 돌면서
        for(String noSee : noSeeArr){
            // set에 noSee가 있을 경우
            if(set.contains(noSee)){
                // answerList에 noSee를 add
                answerList.add(noSee);
            }
        }

        // 문제에 사전 순 정렬하라고 되어있으므로 정렬 처리 해줌
        Collections.sort(answerList);

        // 리턴
        return answerList.toArray(new String[0]);

    }


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

        String[] eachNum = br.readLine().split(" ");

        int[] numArr = Arrays.stream(eachNum).mapToInt(Integer::parseInt).toArray();

        String[] noHear = new String[numArr[0]];
        String[] noSee = new String[numArr[1]];

        for (int i = 0; i < numArr[0]; i++) {
            noHear[i] = br.readLine();
        }

        for(int i=0;i<numArr[1];i++){
            noSee[i] = br.readLine();
        }

        String[] answer = solution(noHear, noSee);

        // 첫 줄은 정답의 개수
        System.out.println(answer.length);

        // 정답 한 줄씩 출력
        for(String ans : answer){
            System.out.println(ans);
        }

    }
}

 

- ArrayList의 contains는 순차탐색하기 때문에 O(n)

- HashSet은 HashMap기반으로 구현되어 있어서, contains을 사용할 경우 HashMap.containsKey()를 불러온다고 함. 따라서 시간 복잡도는 O(1)

-> 따라서 contains를 써야하는 경우, HashSet 자료구조를 사용하는게 더 빠름.