백준 1764 듣보잡 [JAVA]

Ga0·2023년 5월 15일

baekjoon

목록 보기

48/125

문제 해석

첫번째 줄에 듣도 못한 사람의 수(N)과 보도 못한 사람의 수(M)을 입력받는다.
처음에는 N번 듣도 못한 사람의 이름을 입력받는다.
그 다음줄부터는 M번 보도 못한 사람의 이름을 입력받는다.
다 입력 받았다면, 듣도보도못한 사람의 수와 듣도 보도 못한 사람의 이름을 출력하면 된다.
단, 사전순으로 출력하며, 한줄씩 출력한다.

틀린 코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken()); //듣도 못한 사람의 수
        int M = Integer.parseInt(st.nextToken()); //보도 못한 사람의 수

        String[] dArray = new String[N]; //듣도 못한 사람의 명단 저장

        for(int i = 0; i < N; i++){// 듣도 못한 사람의 명단 받기
            dArray[i] = br.readLine();
        }

        Arrays.sort(dArray); //사전 순으로 정렬

        int count = 0; //듣도보도 못한 사람의 수를 저장

        for(int i = 0; i < M; i++){ //보도 못한 사람의 명단 받기
            String str = br.readLine();
            for(int j = 0; j < N; j++){
                if(dArray[j].equals(str)){ //듣도 못한 사람의 명단에도 존재하면
                    count++;
                    bw.write(dArray[j] + "\n");
                }
            }
        }
        br.close();

        System.out.println(count);
        bw.flush();
        bw.close();

    }
}

틀린 결과

시간 초과가 나올 걸 예상했다. (근데도 이렇게 밖에 못푸는..)

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        //중복을 알아서 제거해주는 hashSet
        HashSet<String> set = new HashSet<String>(); //듣도 못한 사람 명단
        for(int i = 0; i < N; i++) {
            set.add(br.readLine()); //학생 이름을 하나씩 넣는다.
        }

        List<String> outSet = new ArrayList<>(); // 출력해야하는 결과
        for(int i = 0; i < M; i++){ //보도 못한 사람의 명단을 입력과 동시에 비교해서 
            String str = br.readLine();
            if(set.contains(str)){ //민약 듣도 못한 사람 명단에 있는 사람의 명단이면
                outSet.add(str); //출력해야하는 결과 ArrayList에 넣어준다.
            }
        }
        //Collections.sort(배열) => 마지막도 hashset을 쓰지 못하는 이유.(정렬할땐 list를 사용)
        Collections.sort(outSet); // 사전 순으로 정렬

        bw.write(outSet.size() +"\n"); //사이즈가 명단에 있는 사람 수가 된다. => 비교해서 넣었으니까
        for(String str : outSet){
            bw.write(str + "\n"); 
        }

        br.close();
        bw.flush();
        bw.close();

    }
}

코드에 대한 설명은 주석으로 작성해두었기 때문에 생략하겠다.

정리한 내용은 아래와 같다.

내가 처음에 시간초과로 틀린 이유는, 배열을 썼기 때문이다.

HashSet의 contain은 O(1)로 ArrayList의 contain는 O(n)로 시간차이가 많이 난다.

비록 틀린 코드에서 contain이라는 함수는 사용하지 않았지만, 사용하지 않았을 뿐 conation의 함수와 유사한 패턴이었다. => 모두 비교해서 2중 for문을 돌렸기 때문

또, HashSet은 map기반으로 구현되고, ArratList은 indexOf()를 사용하여 contain 여부를 결정한다.

이 차이로 시간 차이가 나는 것이다.

indexOf() : (object) 메서드는 전체 배열을 반복하고 각 요소를 equals(object) 메서드와 비교

HashSet-map기반 : 실제로 객체의 위치를 찾기 위해 hashCode() 메서드를 사용, 개체의 버킷 위치를 가져오는 것은 일정한 시간으로 수행한다.