이코테 - 정렬된 배열에서 특정 수의 개수 구하기

 

 

 

풀이

1. 기본적으로는 이진탐색이 배경이 된다.

(찾고자 하는 값보다 현재 값이 작다면 start = mid+1, 반대는 end = mid-1)

 

2. 첫번째 인덱스 찾기

- 현재 인덱스가 0이거나 현재인덱스 -1 에 해당하는 값이 찾고자하는 값보다 작고 현재 인덱스에 해당하는 값이 찾고자하는 값일 때, 종료

- 현재 인덱스의 값이 찾고자하는 값보다 작다면 start = mid+1

- 현재 인덱스의 값이 찾고자하는 값보다 크거나 같다면 end = mid-1

 

예를들어, 1 2 2 2 2 2 3 이 있고 mid는 3이다. 찾고자하는 것은 2의 시작점이다.

인덱스 3에 해당하는 값은 2이다. 해당 인덱스는 0도 아니고 해당 인덱스의 전값이 2보다 작지도 않으므로 첫번째 조건은 성립하지 않는다.

해당 값은 2보다 같거나 크므로 end = mid-1로 줄여 범위를 앞으로 당기고 다음 이진탐색을 실행한다.

 

3. 마지막 인덱스 찾기

- 현재 인덱스가 n-1이거나 현재 인덱스+1에 해당하는 값이 찾고자하는 값보다 크고 현재 인덱스에 해당하는 값이 찾고자하는 값일 때 종료

- 현재 인덱스의 값이 찾고자하는 값보다 작거나 같다면 start = mid+1

- 현재 인덱스의 값이 찾고자하는 값보다 크다면 end = mid-1

 

마찬가지로, 예를 들어, 1 2 2 2 2 2 3 이 있고 mid는 3이다. 찾고자하는 것은 2의 끝점이다.

mid에 해당하는 값은 2이고 mid는 n-1도 아니며 mid+1에 해당하는 값이 3도 아니다. 따라서, 첫번째 조건은 성립하지 않는다.

현재수는 찾고자하는 값과 같으므로 범위를 오른쪽으로 옮겨 다음 이진탐색을 실행해야하므로 start = end+1 처리를 한다.

 

 

 

 

코드 

import java.util.*;

public class Q1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int x = sc.nextInt();
        List<Integer> values = new ArrayList<>();
        for(int i=0; i<n; i++){
            values.add(sc.nextInt());
        }
        
        // 1. find start
        int start = 0;
        int end = n-1;
        int result1 = -1;
        while(start <= end){
            int mid = (start+end)/2;
            int value = values.get(mid);
            if((mid == 0 | value > values.get(mid-1)) && value == x){
                result1 = mid;
                break;
            }
            else if(value < x){
                start = mid+1;
            }
            else{
                end = mid-1;
            }
        }
        
        // 2. find last
        if(result1 != -1){
            start = 0;
            end = n-1;
            int result2 = -1;
            while(start <= end){
                int mid = (start+end)/2;
                int value = values.get(mid);
                if((mid == n-1 | value < values.get(mid+1)) && value == x){
                    result2 = mid;
                    break;
                }
                else if(value <= x){
                    start = mid+1;
                }
                else{
                    end = mid-1;
                }
            }
            System.out.println(result2-result1+1);
        }
        else{
            System.out.println(result1);
        }
    }
}