< 프로그래머스 / 고득점 kit / 이분탐색 > 징검다리

이번 주는 학교 팀플이다 과제다 뭐다 해서 매우 바빳지만 그래도 꾸준히 한문제씩은 알고리즘 문제를 풀으려고 노력했다. 

그러던 도중 알고리즘 유형 별로 나뉘어진 코딩 테스트 고득점 kit 을 발견하였고, 매일 한 분야씩 전부 풀어보려고 노력중이었다. 

내가 지금껏 전혀 사용하지 않았던 알고리즘 풀이 유형인 이분탐색을 공부하고자 했고, 그렇게 만나게 된 문제 두개 다 너무 힘들었다 ㅠㅠ

덕분에 이분 탐색이 뭔지 감을 잡게 된 것 같고, 이분 탐색 유형의 문제를 백준에서 찾아서 좀 더 풀어 보려고 한다. 

 

어디서 본 글인데, '이분 탐색을 제대로 사용하는 프로그래머는 전 세계 10퍼센트도 되지 않는다' 라고 어느 프로그래머가 이야기 했다는데 

무슨 뜻인지 매우 많이 공감이 갔다. logN 이라는 좋은 시간 복잡도를 지녔지만, 섬세하게 다루어야 자잘한 예외 케이스를 맞출 수 있게 된다. 오버플로우.. 언더플로우.. 등등. 그냥 구현만 하면 풀리는 것이 아니라, 이분탐색이라는 탐색 시스템 자체에서 만나는 예외케이스를 공부하고 암걸리고, 고통받으며 2일 동안 공부했다. 

 

이 문제는 프로그래머스 레벨 4 에 있는 문제이다. 풀고 나서 8점 밖에 안주길래, 아직 1300 점도 안됬는데 4레벨에 8점 주면, 무슨 문제를 풀어야 10점 이상을 받나 하는 생각이 잠시 들었다(TMI)

 

https://programmers.co.kr/learn/courses/30/lessons/43236 

코딩테스트 연습 - 징검다리

 

 

징검다리 문제

 

파이참에서 같은 문제를 세번에 걸쳐 코드를 다시 지우고 다시 새로 써보고 했던 것 같다. 

어제부터 쭉 고민해서, 내 고민의 흐름 전부를 전반적으로 세세하게 알려드리기는 힘들지만 문제를 오늘 풀었고, 오늘 코드를 다시 새로 짜면서 고려했던 점 몇가지를 서술 하려고 한다.

( 아마 코드를 전부 짜고, 테스트 케이스에서 몇 문제를 틀리는 분 들이 보면 도움이 될 것 같다 )

 

1. rocks 의 마지막 돌이 파괴 되지 않고, distance(종착점)과의 거리를 비교 했을 때, m ( 이진탐색하는 기준 거리 ) 보다 작다면 어떻게 처리 할 것인가?  --> 파괴된 바위 수 == 파괴해야 하는 바위 수(n) 일지라도, 구해진 m 은 적합하지 않다.

 

2. rocks 의 마지막 돌이 파괴 되었더라도, distance(종착점)과의 거리를 비교했을 때, m ( 이진탐색하는 기준 거리 ) 보다 작다면 어떻게 처리 할 것인가? --> 위와 마찬가지로 적합하지 않은 m 이라는 점.

 

3. 거리의 최솟값의 최댓값이 유효하려면 바위 사이의 거리들중 일치하는 거리가 있어야 한다. --> 처리 안함

 

4. 우리가 짠 코드로 생각하자면, 거리 3 짜리 바위가 4개가 있을 때 ''2개의 바위를 박살 내고 최솟값의 최댓값이 3 이 정답인 케이스가 있을 때''  --> m 이 3 일 때 구해지는 파괴된 바위 수는 n 보다 작은 수가 나올수 있다는 케이스가 있다는 점 ( m 이 2일 때 파괴된 바위수는 1이 나오고, m 이 4 일 때 파괴된 바위수는 5 가 나올 때 )

--> 가령, 우리 코드로는 m 을 3 으로 두었을 때, 파괴된 바위 수는 1개가 나올 수 있다는 점. 거리 3짜리 바위를 하나 더 파괴해서 파괴된 바위수 개수를 맞추면서 3을 어떻게 도춣 할 것인가?

--> 해결은,  파괴된 바위 수 = 파괴해야 하는 바위 수(n) 로 두었던 코드를 ==> 파괴된 바위수 < 파괴해야 하는 바위수(n) 에 합쳐서 넣어 둔다. 

 

1, 2 번의 아이디어를 구현하기 위해, start 로 갱신되기 이전의 위치 backup 변수를 사용해서 그 전전 위치를 저장해서 사용했습니다. 

 

1, 2, 4 번의 아이디어를 코드로 구현한 뒤에 3번 아이디어를 어떻게 코드로 녹일까 고민하기 전에 채점을 해봤는데 100점이 나오길래

3번에 대한 고민은 하지 않았습니다. 

풀고 나서 개인적인 생각으로는 4 번에서 구현한 생각 :

파괴된 바위 수 = 파괴해야 하는 바위 수(n) 로 두었던 코드를 ==> 파괴된 바위수 < 파괴해야 하는 바위수(n) 로 변화시키는 것

이 3 번 아이디어를 해결 했던 것 같습니다.

 

rock_cnt ( 파괴된 바위수 ) == n ( 파괴해야 하는 바위수 ) 이더라도 flag 를 보고 m 이 더 낮아질 수 있다면

계속 m 을 낮추면서 탐색하도록 작동하게 끔 해서 실제로 바위 사이의 거리로 존재하는 최솟값 m 을 구할 수 있지 않았나 라는 생각이 듭니다. 

또한  파괴된 바위수 < 파괴해야 하는 바위수(n) 일 때는 answer 에 m 을 저장하면서, m 의 값을 계속 높이면서 n ( 파괴 해야 하는 바위의 수 ) 를 넘지 않는 선 최대한 바위를 많이 파괴 할 수 있도록(4번의 고민)  탐색을 했기 때문에 가장 높은 m 을 구할 수 있던 것 같습니다.

 

def solution(distance, rocks, n):
    rocks.sort()
    
    s, e, m = 0, distance, 0
    answer = 0
    while s <= e: # n 이 깨진 바위의 개수, 이분탐색은 거리로 한다.
        m = (s + e) // 2
        # print(m)
        rock_cnt, start, flag, backup = 0, 0, True, 0
        for rock in rocks:  ## 마지막 도착점과의 거리를 생각하지 않았다
            d = rock - start
            if d < m: # 바위 파괴
                rock_cnt += 1
            else:
                start, backup = rock, start # backup 에 그 전 start 위치 저장해놓기
    
        if rocks[-1] == start: # 마지막 돌이 파괴 안되고, 목 적지와의 거리가 m 보다 작을 때 -> 마지막돌 파괴해야함
            if distance - start < m:
                rock_cnt += 1
                start = backup # 스타트의 위치를 백업한 스타트의위치로 갱신해놓기
        
        if distance - start < m: # 종점과의 거리가 기준치 m 보다 작을때 --> m 이 더 작아도 똑같이 파괴할수 있다는 뜻
            flag = False # 이 m은 올바른 답이 아니라는 것을 표시
        
        # rock_cnt : 거리의 최솟값의 최댓값이 m 이기 위해서 파괴되어야 하는 바위의 개수
        ## 거리의 최솟값의 최댓값이 유효하려면 바위 사이의 거리들중 일치하는 거리가 있어야 한다. --> 처리 안함
        
        if n < rock_cnt: # 파괴한 바위가 많으면  -> m 줄어야    
            e = m - 1
        else: # 파괴한 바위가 적거나 같을 때
            if flag == False:
                e = m - 1
            else:
                s = m + 1
                answer = m
    
    return answer

 

처음 레벨 4 문제를 접했는데 많이 매웠습니다...

10억 이상의 값을 탐색하는 문제를 이번 이분탐색 kit 를 통해 처음 접했고

매우 즐겁고 유익하게 공부해서 좋았습니다.