2019 카카오 겨울 인턴십 코딩테스트 - 징검다리 건너기(python)

❓ 문제 - 2019 카카오 코딩테스트 징검다리 건너기 문제 - python 풀이법

출처 

(https://programmers.co.kr/learn/courses/30/lessons/64062)

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

 

 

 

📝 문제해결법

 

1. 문제 해결 방법은 일단 구현으로 for문 돌려서 하나씩 stones 확인하면서 하면 시간초과 발생한다. stones 배열의 각 원소값들이 200,000,000 이하이기 때문이다. 

 

2. 따라서 시간 단축을 위해서 이진탐색을 활용해서 문제를 해결한다.

• 이진탐색을 통해 탐색할 것은 건널 수 있는 사람 수를 찾는 것
• 이진 탐색 범위에는 1 ~ 최대 건널 수 있는 사람 수 
• stones 원소들을 for문을 돌면서 각 원소가 건널 수 있는 사람 수보다 작으면, 사용할 수 없는 stone으로 두고 이러한 사용할 수 없는 돌의 갯수를 count , 만약 건널 수 있는 사람 수 보다 큰 stone의 횟수가 되면 count = 0하고
• for문 돌면서 count의 수가 만약 k개보다 크다면 for문 break해서 징검다리를 건널 수 있는 사람 수의 범위 갱신
• count의 수가 k개 보다 작다면, 즉 해당 사람 수로 건넌다면 사용될 수 없는 돌의 갯수가 조건 안에 있으므로 이진탐색의 left 값을 mid+1 로 갱신하면서 건널 수 있는 사람 수의 범위 최솟값을 높인다.
• count의 수가 k개 보다 크다면, 즉 해당 사람 수로 건넌다면 사용될 수 없는 돌의 갯수가 조건에 해당 안되므로 이진 탐색의 right값을 mid-1 로 갱신하고 answer값을 mid 값으로 갱신하면서 건널 수 있는 사람의 수의 범위 최대값을 낮춘다.

3. 이진탐색의 시간복잡도는 O(logN) 이므로모든stones들의 원소를 돌아가면서 확인하는 O(N) 방식보다 효율적이다.

 

 

 

💻 소스코드 

def solution(stones, k):
    answer = 0
    left = 1
    right = max(stones)
    
    while left <= right:
        count = 0
        mid = (left+right) // 2
        for s in stones:
            if s - mid <= 0:
                count += 1
            else:
                count = 0
            
            if count == k:
                break
        
        if count < k:
            left = mid +1
        else:
            right = mid -1
            answer = mid
    
        
    return answer

 

 

 

 

🤷 느낀점

일단 구현방법만 떠오르지 않아서 그걸로 구현했지만 시간초과가 났다. 해당 문제의 카카오 해설을 보니

이진탐색을 이용하면 효율적이게 풀 수 있다고 하였다. 이진탐색이라는 알고리즘을 알고 관련 문제를 풀어보았지만

이러한 문제를 봤을 때 떠올리지 않았다. 앞으로 이진탐색의 알고리즘도 고려해서 문제를 봐야겠다.