[백준]1920 - 수 찾기 문제 풀이(Java,자바)

1920번: 수 찾기

들어가기 앞서

이번 문제는 2가지 방식으로 다시 풀어보았다.

첫 번째 방식은 Set 자료구조를 이용한 방식, 두 번째 방식은 이진 검색을 이용한 방식이다.

처음 문제를 풀 땐, Set을 사용했었는데 다른 사람은 어떻게 풀었는지 검색해보니 이진 검색을 많이 이용한 것을 보고 이를 이용해보았다.

 

1. Set 자료 구조 이용하기

코드

public class 백준1920_수찾기 {
    public static void main(String[] args) throws IOException {
        Set<Integer> set = new HashSet<Integer>();
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        String[] setNumbers = reader.readLine().split(" ");
        for (var s : setNumbers) {
            set.add(Integer.parseInt(s));
        }
        StringBuilder result = new StringBuilder();
        int m = Integer.parseInt(reader.readLine());
        String[] inputs = reader.readLine().split(" ");
        for (var s : inputs) {
            if (set.contains(Integer.parseInt(s))) {
                result.append(1).append("\n");
                continue;
            }
            result.append(0).append("\n");
        }
        System.out.println(result);
    }
}

풀이

특별한 건 없다.

문제에선 값이 있는지 없는지 파악만 하면 되므로 Set을 사용할 수 있다.

검색에 쉽게 사용할 수 있는 HashSet을 이용하여 포함되어 있는지 확인한다.

 

HashSet 이란??

해시테이블을 이용하여 구현된 것으로 내부적으로 HashMap을 사용하여 돌아간다.

순서가 중요하지 않은 상황에서 빠른 검색과 삽입을 요구하는 경우 유용하다.

2. 이진 검색 이용하기

코드

public class 백준1920_수찾기_이진검색 {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        int[] arr = Arrays.stream(reader.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

        Arrays.sort(arr);
        StringBuilder result = new StringBuilder();
        int m = Integer.parseInt(reader.readLine());

        String[] inputs = reader.readLine().split(" ");
        for (var s : inputs) {
            if (search(arr,Integer.parseInt(s))) {
                result.append(1).append("\n");
                continue;
            }
            result.append(0).append("\n");
        }
        System.out.println(result);
    }

    private static boolean search(int[] arr, int goal) {
        int start = 0;
        int end = arr.length - 1;
        while (start <= end) {
            int mid = (start + end) / 2;
            if (goal < arr[mid]) {
                end = mid - 1;

            } else if (goal > arr[mid]) {
                start = mid + 1;
            } else {
                return true;
            }
        }
        return false;
    }
}

 

풀이

그림 1. 이진 탐색 요약

이진 탐색은 오름차순으로 정렬된 배열이나 리스트에서 특정 값을 빠르게 검색할 수 있는 알고리즘이다.

 

배열이 오름차순으로 정렬되어 있다는 가정이 중요하다.

왜냐면 작동 순서가 다음과 같기 때문이다.

1. 시작 인덱스와 끝인덱스가 같지 않다면 2로 진행한다. 아니라면 -1을 리턴한다.

2. 시작 인덱스과 끝인덱스의 중앙 인덱스가 가리키는 값을 현재 찾고자 하는 값과 비교한다.

3-1. 만약 찾고자 하는 값이 중앙 인덱스가 가리키는 값보다 크다면 시작 인덱스를 중앙 인덱스로 바꾼다.

3-2. 만약 찾고자 하는 값이 중앙 인덱스가 가리키는 값보다 작다면 끝 인덱스를 중앙 인덱스로 바꾼다.

3-3. 만약 찾고자 하는 값과 같다면 이 배열의 인덱스를 리턴한다.

4. 1로 돌아간다.

 

배열을 중간으로 계속 잘라가면서 찾고자 하는 범위를 줄이는 방식이다.

그렇기 때문에, 브루트 포스로 찾는 것보다 연산 속도가 빠르다.

 

시간 복잡도

계속 배열을 중간으로 짜르기 때문에 전체 배열의 길이를 N이라고 했을 때, 

그림 2. k번 루프

K 번 진행하면, 그림 2와 같이 계산할 수 있다.

이를 시간복잡도로 생각하면 이진 트리와 같고, 최종적으로

그림 3. 시간복잡도

그림 3과 같은 결과가 나온다.

출처

[백준] 1920번 : 수 찾기 - JAVA [자바]

- 이진 검색 관련

Binary Search Algorithm: Uses, Benefits & Examples | Jaro Education