[코딩테스트] 백준 1920 자바

백준 1920

백준 1920 문제

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

public class Boj1920 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); // 정수의 갯수
        int[] arr = new int[n]; // 정수의 갯수만큼 배열 선언

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

        // 배열 오름차순 정렬 O(n log n)
        Arrays.sort(arr);

        st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken()); // 타겟의 갯수
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) { // 타켓의 수 만큼 반복
            boolean find = false; // 타켓을 찾았는지 확인하는 flag 변수
            int target = Integer.parseInt(st.nextToken()); // target의 값
            int start = 0; // 시작 인덱스
            int end = arr.length - 1; // 마지막 인덱스
            while (start <= end) { // 시작 인덱스와 종료 인덱스의 범위가 좁혀지기 떄문에 시작 인덱스가 마지막 인덱스보다 작거나 같을 때까지만 반복
                int mid = (start + end) / 2; // 중앙값이 위치한 인덱스
                if (arr[mid] > target) { // 중앙값이 타겟보다 크다면
                    end = mid - 1; // 마지막 인덱스를 중앙값의 인덱스 - 1
                } else if (arr[mid] < target) { // 중앙값이 타켓보다 작다면
                    start = mid + 1; // 시작 인덱스를 중앙값 인덱스 + 1
                } else { // 타겟을 찾았다면
                    find = true; // flag 변수 true로 변경
                    break; // 더 탐색할 필요가 없기 때문에 반복문 중단
                }
            }
            if (find) { // target을 찾았으면 1 출력
                System.out.println(1);
            } else { // target이 없으면 0 출력
                System.out.println(0);
            }
        }
        
        br.close();
    }
}

풀이

해당 문제는 제한 시간이 1초이며 N의 최댓값이 100,000으로 O(n2) 시간 복잡도의 알고리즘을 사용하면 제한 시간을 초과하기 때문에 그 이하의 시간 복잡도를 사용해야 한다.

N과 M이 최댓값이 100,000으로 동일하기 때문에 O(n log n)의 시간 복잡도를 가진 자바의 정렬을 사용해도 괜찮다. 그리고 이진 탐색을 사용하면 O(m log n)의 시간 복잡도가 소요되는데, 둘의 알고리즘은 별개로 실행되기 때문에 약 O(2n log n)이 소요된다.

빅오 표기법에서는 상수는 제거가 되기 때문에 O(n log n)의 시간 복잡도를 가진 이진 탐색으로 해당 문제를 풀었다.

1. BufferedReader와 StringTokenizer를 사용하여 정수의 갯수 n값을 입력 받는다.
2. n의 길이만큼의 arr 배열을 선언한다.
3. StringTokenizer로 한 줄을 다시 입력 받고, n만큼 반복하면서 arr 배열에 입력된 정수로 초기화한다.
4. O(n log n)의 시간 복잡도를 가진 Arrays.sort() 메서드로 arr 배열을 오름차순으로 정렬한다.
5. StringTokenizer로 타겟의 갯수인 m을 입력 받는다.
6. StringTokenizer로 한 줄을 다시 입력 받고, m만큼 반복한다.
7. 반복문 안에서 타겟을 찾았는지 확인하는 flag 변수 find를 false로 생성한다.
8. nextToken()으로 target의 값을 하나씩 받는다.
9. 시작 인덱스 start는 0, 마지막 인덱스 end는 arr.length - 1로 생성한다.
10. 시작 인덱스와 종료 인덱스의 범위가 좁혀지기 떄문에 while문을 사용하여 시작 인덱스가 마지막 인덱스보다 작거나 같을 때까지만 반복하도록 한다.
11. 중앙값이 위치한 인덱스 mid를 (start + end) / 2로 구한다.
12. arr[mid] 중앙값이 target보다 크다면, target이 중앙값보다 작은 범위에 있다는 것이기에 end의 값을 mid - 1로 변경한다.
13. arr[mid] 중앙값이 target보다 작다면, target이 중앙값보다 큰 범위에 있다는 것이기에 start의 값을 mid + 1로 변경한다.
14. arr[mid] 중앙값과 target이 같다면, target을 찾았기 때문에 find 변수를 true로 변경하고 break문을 통해 반복문을 중단한다.
15. find의 값이 true이면 target을 찾았기 때문에 1을 출력하고 false이면 못 찾았기 때문에 0을 출력한다.
16. 위 과정을 m번 반복한다.