이진탐색 -효율성을 높이자

가능한 배열속에서 조건을 탐색할 때 시간을 줄여줄 수 있는 방법

정렬된 배열에서 사용하자 정렬이 되어있지 않는 상태에서  정렬을 하고 사용하는건 더 복잡해 지는것 같음 차라리 정렬이 안된 상태에서는 filter를 사용하자

 

 

1. 정렬된 배열에서 a이상의 수의 갯수 구하기

 

계속 효율성에서 시간 초과가 나길래 이진탐색이 생각나서 푸니까 되더라.. 이진탐색을 좀 더 자연스럽게 쓸 수 있도록 연습 해야겠다.

 

 10 9 9 9 8 7 6 6 6 5 4  3 2 2 1 이런 식의 배열에서

 var start = 0
 var end = temArray.size-1
 var posi = 0

 while (start<= end){
     posi = (start+end)/2

     if(temArray[posi].point >=score){
         start = posi+1
     }else{
         end = posi-1
     }
 }
  
  ---- end가 조건에 맞는 포지션

 end 가 맞는 이유를 생각해보면

 

만약 내가 찾고자 하는 위치가 어느 숫자(6이라하자) 6의 마지막 인덱스라고 한다면, 일련의 과정을 통해 

start가 6의 마지막 위치에 존재한다고 한다. 그러면 start가 마지막으로 지정된 위치에서 1칸 뒤로 밀려나게 되고 이 새로운 포지션이 <=end를 만족한다면

end가 계속 변하게 되다가 end포지션이 6의 마지막 자리에 가는 순간 while을 통과하게 된다.

 

발그림으로 표현하자면

이렇게 된다는 뜻임.

 

다르게 생각하면

이렇게 end 위치가 내가 구하고자 하는 position이 된다 다른 것들로 이런식으로 생각해보면 편하다.

 

 

2. 위와 같이 줄어드는 정렬에서 6의 마지막 지점이 아닌 최초지점을 찾고 싶다면

 

class Solution {
    fun solution(info: IntArray, target:Int): Int {
        var start = 0
        var end = info.size-1
        var posi = 0
        while (start<= end){
            posi = (start+end)/2

            if(info[posi] >target){
                start = posi+1
            }else{
                end = posi-1
            }
        }
        println(start)
        return target
    }

 

  

이런식으로 구해보면 된다.

 

3. 정리

 

 머릿속으로 잘 안되어서 임의의 배열을 생각해서 해보니까 좀 더 와닿는다.

 

4. 응용했었던 문제

 프로그래머스의 입국심사문제도 아래와 같이 이용해서 풀어야 했음..

    fun solution(n: Int, times: IntArray): Long {
        var minTime = 1L
        var maxTime = n.toLong() * times.max()!!
        var midTime = 0L
        while (minTime <= maxTime ) {
            midTime = (minTime + maxTime) / 2
            
            val examinedPersonCount = times.fold(0L) {
                    acc, eachDuration ->
                acc + midTime / eachDuration
            }

            if(examinedPersonCount >= n) {
                
                maxTime = midTime - 1
            }
            else minTime = midTime + 1
        }
        return minTime
    }

가능한 범위를 지정해주고 

중간값을 이용하여 조건을 만들어서 

n개를 처리할 수 있는 가능한 시간중 가장 작은 시간을 선택하는 문제로 풀었었음.

 

이렇게 활용을 자유롭게 할 수있을때 까지 해야겠다