[BOJ 길라잡이/Java] 1일차 #1920 수 찾기

알고리즘 분류

- 자료 구조

- 정렬

- 이분 탐색

- 해시를 사용한 집합과 맵

 

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

 

처음 생각나는 가장 쉬운 방법은

문제에 주어진 것처럼 int[] 배열 A에

N개의 숫자를 넣고

 

M개의 수들을 순서대로

배열A 안에 있는지 확인하는 것이다.

 

그런데 그렇게 되면 2중으로 최대 N * M 만큼 돌게 되고

O(N * M)

10^5 * 10^5 = O(10^10)

1초에 약 10^8 ~ 10^9번의 연산을 수행할 수 있다고 가정했을 때

최악의 경우 10초도 넘을 수 있다!

 

따라서 다른 방법이 필요하다.

 

HashSet 사용

예전에 풀 때 위처럼 N*M 방법을 사용하다가 시간 초과가 나서

구글링해 풀었던 방법이다.

HashSet을 사용하면 O(N + M)로 문제를 해결할 수 있다.

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));
        int N = Integer.parseInt(br.readLine());
        HashSet<Integer> A = new HashSet<>(); // hashset 사용

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A.add(Integer.valueOf(st.nextToken()));
        } // N개의 원소를 HashSet에 넣으므로 O(N)

        int M = Integer.parseInt(br.readLine());
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int j = 0; j < M; j++) { // O(M)
            int num = Integer.parseInt(st2.nextToken());
            if (A.contains(num)) { // O(1)의 시간 복잡도
                sb.append(1);
            } else {
                sb.append(0);
            }
            if (j != M - 1) sb.append("\n");
        }
        System.out.println(sb);
    }
}

StringBuilder를 이용한 출력은 O(1)에 가까우므로

O(N+M)의 시간 복잡도를 가지게 된다.

 

HashMap 사용

이건 내가 두 번째 혼자 힘으로 풀었을 때 사용한 방법이다.

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));
        int N = Integer.parseInt(br.readLine());
        HashMap<Integer, Integer> map = new HashMap<>();

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            map.put(Integer.parseInt(st.nextToken()), 1);
        }

        int M = Integer.parseInt(br.readLine());
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        for (int j = 0; j < M; j++) {
            int num = Integer.parseInt(st2.nextToken());
            if (map.getOrDefault(num, 0) == 1) {
                System.out.println(1);
            } else {
                System.out.println(0);
            }
        }
        
    }
}

N개의 숫자들을

HashMap에 value 1로 저장해준다.

이후 M개의 숫자를 돌며 map에서 해당 key(M)의 value가 1인 경우 1 출력,

아닌 경우 0을 출력하는 방법이다.

 

요 방법도 HashMap의 put과 get 메서드가 평균적으로 O(1) 이므로

전체적으로 O(N+M)의 시간복잡도를 가진다.

 

System.out.println으로 한 줄씩 출력하지 않고

위에 쓴 것처럼 StringBuilder를 이용해 한 번에 출력해주면

시간 복잡도를 더 줄일 수 있다!

 

정렬과 이분 탐색 사용

이건 이후 구글링을 통해 알게 된 새로운 문제 접근 방식이다.

 

킥은 "정렬"이다.

정렬을 해주지 않으면 이분 탐색을 사용해서 찾을 수 없다.

이분 탐색의 시간복잡도는 O(log N)이다.

정렬 후 이분 탐색을 하는 알고리즘의 시간복잡도는 O(N log N)이다.

요 문제에서는 O((N+M) log N)이 된다.

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));

        // N 입력 받음
        int n = Integer.parseInt(br.readLine());

        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        // N개의 정수 배열을 오름차순으로 정렬
        Arrays.sort(arr); // 퀵소트 사용하여 평균적으로 O(NlogN)이 걸림

        int m = Integer.parseInt(br.readLine());

        // 결과를 저장하는 StringBuilder
        StringBuilder sb = new StringBuilder();

        // M개의 수들을 입력 받고, 이 수들이 N개의 정수 배열에 존재하는지 확인하여 결과를 StringBuilder에 추가
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) { // M개 수에 대해 이진 탐색이므로 O(MlogN)
            int num = Integer.parseInt(st.nextToken());

            // 이진 탐색으로 M개의 수가 N개의 정수 배열에 존재하는지 확인
            int in = Arrays.binarySearch(arr, num); // O(logN)

            if (in < 0) {
                sb.append(0 + "\n"); // 존재하지 않으면 0을 StringBuilder에 추가
            } else {
                sb.append(1 + "\n"); // 존재하면 1을 StringBuilder에 추가
            }
        }

        // 최종 결과 출력
        System.out.println(sb);
    }
}

코드 출처: https://propercoding.tistory.com/319

 

Arrays.binarySearch() 함수가 있는걸 처음 알게 됐다.

이 함수는 찾지 못 했을 경우 음수를 반환한다고 한다.