[프로그래머스] (Swift) 징검다리 (lv.4, 이분탐색) (테케 2,3 시간초과)

⚫️ 문제

https://school.programmers.co.kr/learn/courses/30/lessons/43236?language=swift 

프로그래머스

 

⚫️ 나의 풀이

이 문제 또한 이분탐색으로 분류가 되어있었기 때문에 파라메트릭 서치로 풀어야겠다, 싶은 감이 왔던 거지 그게 아니라면 알기 쉽지 않을 것 같다. 하지만 가장 먼저 눈에 보이는건 10억이라는 어마어마한 범위. 이것만이 이분탐색일 것이다 ~ 하는 감?을 줄 뿐이다. 

처음에는 역시나, 문제를 보자마자 어떤 것을 이분탐색의 대상으로 주어야할지 너무 고민이었다. 처음에 생각한건, 돌의 간격의 최소를 찾는 과정이기 때문에 돌의 간격을 무조건적으로 left 와 right로 두고 탐색을 진행해야한다고 생각했다. 그럼.. 돌은 뭐 어케 삭제함? 삭제한 돌을 기준으로 간격을 생각해야하는데 그거 어떻게 적용시킬건데1?!!? 

우리가 돌의 간격을 고려해서 최소값을 찾을 때 또하나의 조건을 고려해야한다. '돌이 삭제되는 개수!'이다. 주어진 n개만큼만 삭제되어야하는데, 이것을 파라메트릭 서치로 활용할 수 있지 않을까?

예를들어, 돌이 삭제된 개수가 n개 이상이면?? → 너무 많이 삭제된거야! → 삭제 되는 돌의 개수를 줄이려면 어떻게 접근해야하지?

이렇게 생각할 수 있겠다... 그리고 여기서 생각이 막혔다. 어떤 조건을 주었길래 돌이 많이 삭제되는거지 ? ㅋㅋㅋㅋㅋ 그니까 돌은 왜 무슨조건때문에 삭제여부가 결정되는건데!! 꼬리에 꼬리를 물고 문제를 해결할 수 있는 해결책은 보이지 않았다. ㅋㅎㅋㅎ... 하 여렵고만

인터넷을 살짝 참고했다. 참고하면서 아래 블로그의 생각전개방식이 내 생각과 조금? 비슷했고 자세히 써주셔서 어떻게 생각을 흐르게 해야할지 조금 감을 잡을 수 있었다.

https://velog.io/@cgw0519/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%A7%95%EA%B2%80%EB%8B%A4%EB%A6%AC

[알고리즘 문제풀이] 프로그래머스 징검다리

 

음, 다시 돌아가서 처음부터 생각해보자. 우선 left, right, mid가 멀 의미하는지 잘 알아야한다. 우리가 이분탐색을 하면서 구하려는 값은 mid 이다.  조건을 모두 만족하는 mid 값을 구하는것! 이것을 자꾸 까먹어서,,, 생각하기가 쉽지 않았다.  초반에 생각한것 처럼, 돌 사이의 간격을 left와 right으로 두면, mid값이 타겟값이 되었을때! 우리는 해를 구할 수 있다. 그렇다면, 우리는 가장 큰 범위의 distance 가 될 수 있는 값을 right로 두고, 가장 적은 distance가 나올 수 있는 거리를 left로 두면 되지 않을까? 그리고 mid는 (left + right) / 2 해서 구할 수 있을 것이다. 

그럼, 현재 상태에서는 돌을 2개만 삭제해서, 돌사이의 거리의 최소가 12가 되어야한다. 돌들을 돌아보면서 판단해보면, 

1. 첫번째 2번돌 → 간격은 0~2니까 2 → 2는 mid인 12보다 작으므로, 12가 최소가 될 수 없음 → 삭제된 돌일 것이야
2. 두번째 11번돌 → 간격은 0 ~ 11니까 11 (2번돌은 삭제되어서 없다.) → 11은 mid인 12보다 작으므로, 12가 최소가 될 수 없음 → 삭제된 돌일 것이란 말이다
3. 세번째 14번돌 → 간격은 0~14니까 14 (2,12번은 삭제) → 14는 mid인 12보다 크므로, 12가 최소가 될 수 있음 → 이돌은 살려
4. 네번째 21번돌→ 간격은 14 ~ 21니까 7 → 7 < 12 → 이 돌도 죽여야해
....... 🔁 반복

이렇게 될 것이다. 이분탐색은, mid 가 일단 미리 정해진 답이라고 생각하고, 그다음 해를 구해보고 그 해가 내가원하는 해가 아니라면? 처음부터 다시 미리정해진 답을 설정한다.라고 이해하면 이해가 쉬울 것 같다. 현재 이것도 mid인 12가 최소일거야! 하고 설정해두고, 12가 최소가 되지 않는 값들은 없는 돌일거야~ 하고 돌들을 삭제했다. 결국 n보다 많은 돌들이 삭제됐고, 그렇다면 12는 답이 아니라는 뜻이 된다.

그럼,,, left ~ mid 와 mid~right 를 설정하는 조건은 어떻게줄까? 이건 삭제된 돌의 개수를 보자. 위의 경우에서 삭제되어야하는 돌 , 즉 주어진 n은 2인데, 현재 2개 이상의 돌이 삭제된 상태다. 그렇다면 최소간격 12를 줄여야 삭제되는 돌의 개수를 줄일 수 있을 것이다. 

mid = (left + right) / 2로 설정되어있으니, mid를 줄이기 위해서는 right를 left쪽으로 끌어오는 방법이 있겠지? 그럼 right를 mid - 1로 설정해줄 수 있겠다.

 

아래 노트는 위의 과정을 이해하고 생각해낸 아이패드에서 끄적여놓은 노트이다...

 

⚫️ 자 그럼 이것을 코드로 구현해서 제출해보자

import Foundation

func solution(_ distance:Int, _ rocks:[Int], _ n:Int) -> Int {
    var rocks = rocks
    rocks.append(0)
    rocks.append(distance)
    rocks.sort()

    var left = 0
    var right = distance
    var answer = 0

    while left <= right {
        let mid = (left + right) / 2
        var preRock = rocks[0]
        var removeRock = 0
        var minDistance = 1000000001

        for i in 1..<rocks.count {
            if rocks[i] - preRock < mid {
                removeRock += 1
            } else {
                minDistance = min(rocks[i] - preRock, minDistance)
                preRock = rocks[i]
            }
        }

        if n >= removeRock {
            answer = minDistance
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return answer
}

읭? 테케 2,3, 시간초과???? 

 

풀이방법은 틀린게 없다고 확신하여 sort되는 부분을 유심히 봤다. 파라메트릭 서치 (이분탐색)을 진행할 때는 정렬되어있는 배열을 사용해야하기 때문에 sort하는데 시간이 더 걸릴 것이라고 판단했다. 

여기서 쓸데 없는 코드를 발견했다. sort를 다른 메서드로 바꿔야하나? nlogn을 보장하는 것으로 바꿔야하나? 싶었는데, 아닌것 같았고, 내가 append 로 0과 distance를 더 넣어줌으로써 sort하는 시간이 더 걸리는 것 같았다. 사실 애초에 left와 right는 그냥 0과 distance 상수값으로 설정해주면 되는 것이고, 굳이 rocks에 추가하지 않아도 된다. rocks에 새로운 값을 추가해줌으로써 만약 rocks의 배열이 아주 크게 들어오게 됐을때, 두개의 값을 더 추가해줌으로써, 정렬하는데 시간이 n번 더 걸릴 것이다. 이것 때문에 초과하지 않았을까? 

역시나! 이거 고치니까 해결완료 되는군

 

⚫️ 정답코드

import Foundation

func solution(_ distance:Int, _ rocks:[Int], _ n:Int) -> Int {
    let rocks = rocks.sorted()
    var left = 0
    var right = distance
    var answer = 0

    while left <= right {
        let mid = (left + right) / 2
        var preRock = 0
        var removeRock = 0
        var minDistance = 1000000001

        for rock in rocks {
            if rock - preRock < mid {
                removeRock += 1
            } else {
                minDistance = min(rock - preRock, minDistance)
                preRock = rock
            }
        }

        if n >= removeRock {
            answer = minDistance
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return answer
}

 

 

자, 이제 앞으로 이분탐색 문제를 풀때 기억해야하는 것은 이것이다.
우리가 이분탐색으로 구하려고 하는 mid 타겟값은 '해'이고, 파라메트릭 서치로 이 해가 맞는지 아닌지 확인한다. mid가 해 라는것을 잊지 말자!