[BOJ] 1920번: 수 찾기

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

 

이 문제는 입력한 수들이, 앞선 배열에 요소로 들어가 있는지 탐색하여 결과를 출력하는 문제다. 

사실 이진 탐색을 써야만 할 것 같았지만 머릿속에 떠오른 방법이 있어 우선 아래 방법을 시도해보았다.

 

시도 1) 추가 배열 인덱스로 찾기

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

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

        for (int i = 0; i < N; i++) {
            arrN[i] = Integer.parseInt(st1.nextToken());
            int value = arrN[i];
            exist[value] = 1;
        }

        int M = Integer.parseInt(br.readLine());
        int[] arrM = new int[M];
        StringTokenizer st2 = new StringTokenizer(br.readLine());

        for (int i = 0; i < M; i++) {
            arrM[i] = Integer.parseInt(st2.nextToken());
            int value = arrM[i];

            if(exist[value] == 1)
                System.out.println(1);
            else System.out.println(0);
        }
    }
}

 

exist라는 이름으로 배열 요소가 존재하는지, 존재하지 않는지 파악하는 배열을 만들어준다.

arrN 배열에 요소로 입력한 값을 인덱스로 하여, 존재하면 exist[i]=1로 바꿔주었다. 예를 들어 arrN[i] = 5라고 하자. 그럼 exist[5]=1을 넣어준다. exist의 나머지 배열 칸은 0으로 채워져있기에, 추후 배열 arrM의 값이 arrN에 있는지는 exist[arrM[i]] (0 혹은 1임)을 출력하면 된다.

 

예제의 입력으로는 출력이 잘 나오긴 하지만 사실 이 문제와는 맞지 않는 코드였다...

 

"모든 정수의 범위는 -2^31보다 크거나 같고 2^31보다 작다."

arrN의 값(A[1], A[2], ...)이 들어가는 exist 배열의 인덱스에, 음수도 못 넣을뿐더러 저렇게 큰 배열을 만들기도 힘들다.

 

❗️문제 조건을 항상 유심히 읽어보자

 

어쨌든 이와 같은 이유로... 이진 탐색으로 다시금 코드를 짜기로 결정했다.

 

---

시도 2) 이진 탐색

이진 탐색은 정렬된 배열을 반씩 잘라 비교하여 탐색하는 방법이다. 내가 찾으려는 값이 배열의 중간 지점 요소와 값이 같다면 탐색에 성공한다. 만약 중간 지점 요소보다 내가 찾으려는 값이 크면 반으로 자른 배열의 오른쪽 부분에 한해서 다시 이진 탐색을 반복한다. (이 오른쪽 배열의 중간 지점 요소와 비교) 또한, 중간 지점 요소보다 내가 찾으려는 값이 작으면 처음에 반으로 자른 배열의 왼쪽 부분에 한해서 다시 이진 탐색을 반복한다.

 

필요한 건 정렬된 배열, 반으로 배열을 쪼개기 위한 인덱스가 될 시작점, 끝점, 내가 찾는 값과 비교할 중간지점, 그리고 값을 찾을 때까지 반복할 재귀함수이다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

// 이진 탐색
public class BOJ_1920_2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arrN = new int[N];

        StringTokenizer st1 = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; i++) {
            arrN[i] = Integer.parseInt(st1.nextToken());
        }

        Arrays.sort(arrN);

        int M = Integer.parseInt(br.readLine());
        int[] arrM = new int[M];
        StringTokenizer st2 = new StringTokenizer(br.readLine());

        for (int i = 0; i < M; i++) {
            arrM[i] = Integer.parseInt(st2.nextToken());
            arrM[i] = binarySearch(arrM[i], arrN, 0, arrN.length-1);
            System.out.println(arrM[i]);
        }
    }

    public static int binarySearch(int num, int[] arr, int start, int end) {
        if(start > end)
            return 0;

        int mid = (start+end)/2;

        if (num < arr[mid])
            return binarySearch(num, arr, start, mid-1);

        else if (num > arr[mid])
            return binarySearch(num, arr, mid+1, end);

        else return 1;
    }
}

binarySearch 함수의 return 값을 0 또는 1로 하여 바로 바로 결과가 출력되게 하였다.

개인적으로 조금 헷갈렸던 것은 탐색을 마치는 조건이었다. num == arr[mid]일 때까지(배열에 있을 때까지), 혹은 계속 반복 했지만 배열에 없어 더 이상 배열을 반씩 쪼갤 수 없을 때까지 반복하는 것이기에 고민을 했는데, start>end 이면 return 0;(배열에 없음)으로 조건을 두면 된다.

 

그리고 "내가 찾으려는 값이 mid에 위치하는 값과 비교했을 때 작거나 크다면 특정 구간으로 다시금 binarySearch를 시도하기"라는 논리를 토대로 재귀함수를 사용하고 있기에, 메소드 안에서 메소드를 다시 호출할 때 이름만 호출하지 않고 return까지 붙여주자. 이걸 처음에 빼먹어서 에러가 났었다.  

 

---

역시 또 중요한 건 조건 꼼꼼히 읽기.. 그래도 내가 생각한 논리대로 코드를 짜봤다는 뿌듯함을 느꼈다!