99클럽 코테 스터디 19일차 TIL + 이분탐색

 

Sort 마스터 배지훈의 후계자

 

 

문제

지훈이는 Sort 마스터다. 오랫동안 Sort 마스터 자리를 지켜온 지훈이는 이제 마스터 자리를 후계자에게 물려주려고 한다. 수많은 제자들 중에 후계자를 고르기 위해서 지훈이는 제자들에게 문제를 준비했다. 먼저 제자들에게 N$N$개의 원소를 가진 배열A$A$를 주고, A$A$의 원소들이 오름차순으로 정렬된 배열B$B$를 만들게 한다. 그다음 M$M$개의 질문을 한다. 각 질문에는 정수 D$D$가 주어진다. 제자들은 주어진 정수D$D$가 B$B$에서 가장 먼저 등장한 위치를 출력하면 된다. 단, D$D$가 B$B$에 존재하지 않는 경우에는 -1를 출력한다. Sort 마스터의 자리를 너무나도 물려받고 싶은 창국이를 위해 지훈이의 문제를 풀 수 있는 프로그램을 만들어 주자.

입력

첫째 줄에 배열A$A$의 원소의 개수 N$N$과 질문의 개수 M$M$이 공백으로 구분되어 주어진다.

다음 줄부터 N$N$줄에 걸쳐 정수 A0,A1,...,AN−1$A_0, A_1, ... , A_{N-1}$이 주어진다.

다음 줄부터 M$M$줄에 걸쳐 정수 D$D$가 주어진다.

출력

 M$M$개의 질문에 대해서 주어진 D$D$가 B$B$에서 처음으로 등장한 위치를 출력한다. 단, 존재하지 않는다면 -1를 출력한다. (배열에서 가장 앞의 원소의 위치는 0이다.)

제한

• 1 ≤ N$N$ ≤ 2×105
• 1 ≤ M$M$ ≤ 2×105
• -109 ≤ Ai$A_i$ ≤ 109
• -109 ≤ D$D$ ≤ 109

예제 입력 1 

5 5
9
0
-1
3
2
-1
10
5
9
0

예제 출력 1 

0
-1
-1
4
1

예제 입력 2 

8 4
3
3
4
9
2
5
3
4
3
10
4
2

예제 출력 2 

1
-1
4
0

 

---

 

 

 

- 배열 원소 개수와 질문의 개수 받아와서 

- 배열을 오름차순으로 정렬한 배열을 생성하고

- 질문의 정수가 정렬된 배열 원소 몇 번째에 있는지 출력한다.

 

 

! 이 문제의 핵심은

-> 정렬된 배열에서 특정 숫자가 처음 등장하는 위치를 찾는 것 

 

이진탐색 

을 이용하자

 

 

 

<1차 코드>

import java.util.Arrays;
import java.util.Scanner;

public class DAY19 {
    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); //배열 원소 수
        int m = sc.nextInt(); // 질문 수
        sc.nextLine();

        int[] arr = new int[n];
        int[] sort_arr = new int[arr.length];

        for(int i=0; i<n; i++){
            sc.nextInt(arr[i]);
        }

        Arrays.sort(arr);

        for(int i=0; i<n; i++){
            sort_arr[i] = arr[i];
        }


        //질문 수
        for(int i=0; i<m; i++){
            int query = sc.nextInt();

            //만약 받아온 query가 sort_arr[i]에 있을 때
            //i 값 반환
        }

    }
}

 

- sc.nextInt(arr[i])은 잘못된 문법임. -> arr[i] = sc.nextInt()로 변경

- arr을 정렬하고 복사할 필요 없음. 그대로 쓰면 됌.

- 오름차순 정렬 후 -> 정렬되어 있으므로 이진탐색 사용

 

 

 

	for(int i = 0; i < m; i++){
            int query = sc.nextInt();

            int idx = lowerBound(arr, query);

            // 배열의 끝이 아니고, 해당 위치에 값이 query와 같다면 위치 출력
            if (idx < n && arr[idx] == query) {
                System.out.println(idx);
            } else {
                System.out.println(-1);
            }
        }

 

- 받아온 원소를 query에 저장하고,

 

 

<lowerBound 함수>

 

private static int lowerBound(int[] arr, int target) {
    int left = 0;
    int right = arr.length;

    while (left < right) {
        int mid = (left + right) / 2;

        if (arr[mid] < target) {
            // target보다 작으면 무조건 왼쪽 아니야
            left = mid + 1;
        } else {
            // 같거나 크면 가능성이 있으니까 줄이기
            right = mid;
        }
    }

    return left;
}

 

예시로 arr = [1, 3, 3, 3, 5, 7, 9]

target이 3일 때 결과는 1(1번 인덱스)이어야 함.

 

1)

- mid = 0+7/2 = 3

- arr[3] = 3, 3>=target 이므로 right= 3

 

2) 

- mid = 0+3/2 = 1

- arr[1] =3, 3>=target 이므로 right =1

 

3)

- mid = 0+1/2 = 0

- arr[0] = 1, 1<target 이므로 left는 0+1

-> left == right ==1이므로  끝

 

 

** 질문 

 

왜 left를 반환하는가?

=> 이진 탐색이 끝났을 때 left가 원하는 target이 들어갈 수 있는 가장 왼쪽 자리를 가리키기 때문이다.

 

 

 

**중요

lowerBound(arr, query)

는 정렬된 배열 arr에서 query라는 값이 처음으로 등장하는 위치를 찾는다는 의미

 

즉, 정렬된 배열에서 특정 값의 첫 위치를 찾는 이진 탐색 함

 

-> 자바의 Arrays.binarySearch()를 사용하면 안되는가?

= 이는 정확히 일치하는 값 하나만 찾는 것이므로 중복값이 있을 경우 처음 등장하는 위치를 찾기 어렵다.

 

 

<최종 코드>

 

import java.util.Arrays;
import java.util.Scanner;

public class DAY19 {
    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); //배열 원소 수
        int m = sc.nextInt(); // 질문 수
        sc.nextLine();

        int[] arr = new int[n];

        for(int i=0; i<n; i++){
            arr[i] = sc.nextInt();
        }

        Arrays.sort(arr);


        //질문 수
        for(int i=0; i<m; i++){
            int query = sc.nextInt();

            int indx = lowBound(arr,query);

            if(indx<n && arr[indx] == query){
                System.out.println(indx);
            }else{
                System.out.println(-1);
            }

        }

    }

    private static int lowBound(int[] arr, int target){
        int left =0;
        int right = arr.length;

        while(left<right){
            int mid = (left + right)/2;

            if(arr[mid] < target){
                left = mid +1;
            }else{
                right = mid;
            }
        }

        return left;
    }
}

 

 

- 정렬 어렵다.

- 셤 기간 이슈로 오랜만에 스터디 출석하는듯

- 이전 정렬문제 더 풀어봐야겠