[BOJ 길라잡이/Java] 3일차 #10815 숫자 카드

알고리즘 분류

- 자료 구조

- 정렬

- 이분 탐색

- 해시를 사용한 집합과 맵

 

상근이가 가지고 있는 숫자 카드 개수 N(1 <= N <= 500,000)이 주어지고

숫자 카드에 적혀 있는 정수가 주어진다. (-10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.)

셋째 줄에는 M(1 <= M <= 500,000)이 주어지고

넷째 줄에는 M개의 정수가 주어지며 공백으로 구분된다 (-10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.)

 

문제를 읽자마자

주어지는 정수가 범위가 엄청 크므로 시간 제한에 조심해야 겠다는 생각이 들었다.

 

ArrayList를 만들어 상근이가 가지고 있는 카드 정수들을 모두 넣고

M개의 정수를 돌며 ArrayList 안에 있는지 contains 메서드로 확인하면 되지 않을까 생각했다.

 

그런데 이렇게 문제를 푸니 시간 초과가 났다.

아래 코드와 같이 작성했었다.

 

ArrayList 사용 (실패 코드)

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        ArrayList<Integer> cards = new ArrayList<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            cards.add(Integer.parseInt(st.nextToken()));
        } // O(N), ArrayList.add()는 O(1)이므로

        int M = Integer.parseInt(br.readLine());
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            int num = Integer.parseInt(st2.nextToken());
            if (cards.contains(num)) { // ArrayList.contains()는 순차 탐색, O(N)
                sb.append(1);
            } else {
                sb.append(0);
            }
            sb.append(" ");
        }

        System.out.println(sb.toString());
    }
}

여기서 조심해야 했던 부분은

cards.contains(num)으로 ArrayList.contains()를 사용하는 부분이다.

contains()를 내부적으로 리스트를 처음부터 끝까지 순차 탐색하는 방식이므로 O(N)의 시간 복잡도를

가지고 있었다.

이 루프는 M번 반복되므로 O(N * M)이 되는 문제가 생겼다.

 

각각 50만이 최대 입력 크기 이므로

O(500,000 * 500,000) = O(250,000,000,000)

2초를 훌쩍 넘는 시간이 된다.

 

따라서 다른 방법을 고민해 보았다.

 

HashSet 사용 (성공 코드)

중복되는 숫자를 한 번에 저장해두어도 되는 문제이므로

HashSet에 넣으면 되지 않을까 생각했다.

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        HashSet<Integer> cards = new HashSet<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            cards.add(Integer.parseInt(st.nextToken()));
        }

        int M = Integer.parseInt(br.readLine());
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            int num = Integer.parseInt(st2.nextToken());
            if (cards.contains(num)) { // HashSet.contains()는 O(1)
                sb.append(1);
            } else {
                sb.append(0);
            }
            sb.append(" ");
        }

        System.out.println(sb.toString());
    }
}

HashSet.contains()는 ArrayList.contains()의 순차 탐색과 달리

O(1)의 시간 복잡도를 가지므로 M번 실행되는 루프를 돌면

O(M)이 된다.

따라서 시간 내 성공할 수 있다.

 

그럼 둘 다 contains() 메소드인데 무엇이 다른걸까?

HashSet.contains() vs ArrayList.contains()

HashSet은 해시 테이블을 기반으로 구현된다.

contains() 호출 시에 입력된 값의 해시 코드를 계산한 후,

해당 캐시값이 저장된 버킷을 찾아서 비교한다.

따라서 평균적으로 O(1)의 시간 복잡도를 가진다.

(그러나 요소의 순서가 보장되지 않는다는 특징을 가진다.)

 

ArrayList는 배열 기반으로 구현된다.

contains() 호출 시에 리스트의 첫 번째 요소부터 마지막 요소까지 순차적으로 비교한다. (Linear Search)

시간 복잡도가 O(N)이다.

 

찾아보니 이진 탐색을 사용해서 푸는 방법도 있었다.

이분/이진 탐색 사용

이진 탐색은 시간 복잡도가 O(logN)이므로 O(N)보다 빠르다.

 

이진 탐색을 위해서 정렬을 진행한다.

1. 초기 값으로 left = 0, right = n을 저장한다.

2. mid는 left와 right의 중간값으로 설정한다.

3. arr[mid]와 num을 비교한다.

- arr[mid] > num인 경우 left = mid + 1을 하고 2~3을 반복한다.

- arr[mid] < num인 경우 right = mid - 1을 하고 2~3을 반복한다.

- arr[mid] == num인 경우 num을 찾았으므로 반복을 종료한다.

4. num을 찾지 못하고 반복문이 종료된 경우 찾지 못한 것이다.

 

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

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, M;
    static int arr[];

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0 ; i < N; i++)
            arr[i] = Integer.parseInt(st.nextToken());

        // 숫자 카드 오름차순 정렬
        Arrays.sort(arr);

        M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        for(int i = 0 ; i < M; i++) {
            int num = Integer.parseInt(st.nextToken());
            // 이분 탐색을 해서 해당 숫자가 있는 경우
            if(binarySearch(num)) bw.write("1 ");
            // 이분 탐색을 해서 해당 숫자가 없는 경우
            else bw.write("0 ");
        }

        bw.close();
        br.close();
    }
    private static boolean binarySearch(int num) {
        int leftIndex = 0;
        int rightIndex = N - 1;

        while(leftIndex <= rightIndex){
            int midIndex = (leftIndex + rightIndex) / 2;
            int mid = arr[midIndex];

            if(num < mid) rightIndex = midIndex - 1;
            else if(num > mid) leftIndex = midIndex + 1;
            else return true;
        }
        return false;
    }
}

 

아래서부터 순서대로

HashSet 사용 -> ArrayList 사용 -> 이분 탐색 사용