[Code Tree] Binary Search - 숫자 빠르게 찾기 [해결] [코드트리 조별과제]

 

n개의 숫자가 오름차순으로 정렬된 상태로 주어집니다. 이후 m개의 숫자가 추가적으로 주어졌을 때,
각각의 숫자가 처음 주어진 n개의 숫자 중 몇 번째로 나온 숫자인지를 구하는 프로그램을 작성해보세요.

첫 번째 줄에는 n, m이 공백을 두고 주어집니다.

두 번째 줄에는 n개의 숫자가 공백을 사이에 두고 주어집니다. 단, n개의 숫자는 오름차순으로 정렬되어 주어지며, 주어지는 모든 숫자는 서로 다름을 가정해도 좋습니다.

세 번째 줄 부터는 m개의 줄에 걸쳐 숫자가 한 줄에 하나씩 주어집니다.

1 ≤ n, m ≤ 100,000

1 ≤ 주어지는 값 ≤ 1,000,000,000

m개의 줄에 걸쳐 주어진 각 숫자가 처음 주어진 n개의 숫자들 중 몇 번째 숫자로 나왔는지를 출력합니다. 
만약 n개의 숫자 그 어디에도 나와있지 않는다면, -1을 출력합니다.

입력:

5 7
1 5 7 9 10
1
2
5
6
7
9
10

출력:

1
-1
2
-1
3
4

 

라는 문제를 해결하였습니다.

 

결국 처움 주어진 n개의 숫자 중 몇번째로 나온 숫자인지를 구하는 프로그램입니다.

 

접근 방식

저는 일단 처음 주어진  n개의 숫자중 몇번째로 나온 숫자를 구해야한다라는 점을 Point로 잡았습니다. 

N개의 숫자들을 배열에 담아 M에 맞춰서 존재하는가 안하는가를 따져보았습니다. 일단 시간복잡도는 N이 100000이기때문에 O(N) 또는 O(NlogN)인 방식으로 접근해야합니다. 

배열중에 M이 존재하는지 또한 존재한다면 몇번째에 존재하는가? 를 생각해보았을때 우리는 N개의 배열에서 순서대로 찾아봐야합니다. 

1,5,7,9,10 중 M이 7이라면 답은 3 입니다. M이 10이라면 답은 5겠죠?  직관적으로 본다면 NM로 풀어야겠지만 우리는 시간초과 문제로 이진탐색을 사용하여 풉니다 O(MlogN)을 사용하여 푸는 방법입니다.

 

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

public class Main {
    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 M = 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());
        }

        Arrays.sort(arr);

        for(int i=0; i<M; i++){

            int left=0;
            int right=N-1;
            int ans=-1;
            int mid = N/2;
            int target = Integer.parseInt(br.readLine());

            while(true){
                
                mid = (left+right)/2;
                if(left>right){
                    break;
                }

                if(arr[mid]==target){
                    ans=mid+1;
                    break;
                }

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

            }
            System.out.println(ans);
        }
        // 여기에 코드를 작성해주세요.
    }
}

 

"임의"로 값을 설정하여 원하는 target값이 존재한다면 답을 출력하지만 임의값이 target보다 작다면? 임의의값을 target쪽으로 가야하니 중간값을 더 오른쪽으로 이동시켜야합니다 => left =mid+1, 그렇다면 임의값이 target값보다 크다면 중간값을 왼쪽으로 이동시켜야합니다 => right=mid-1;

임의의값이 target값보다 작다면 => 임의의값을 크게 만들어야한다 => 오른쪽으로 이동시켜야한다 => left 영향

임의의값이 target값보다 크다면 => 임의의값을 작게 만들어야한다 => 왼쪽으로 이동시켜야한다 =>right 영향

 

이런식으로 문제를 해결하였습니다.