[프로그래머스] <징검다리> 파이썬

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

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

def solution(distance, rocks, n):
    rocks.sort()
    start, end = 0, distance
    answer = 0
    while start <= end :
        cnt = 0
        temp = distance
        current = 0
        mid = int((start+end)/2)
        for i in range(len(rocks)) :
            dist = rocks[i] - current
            if dist > mid : 
                temp = min(temp, dist)
                current = rocks[i]      
            else : 
                cnt += 1

        if cnt > n : end = mid - 1
        else : 
            answer = temp
            start = start + 1
    return answer
        

정확성 테스트

테스트 1 〉	통과 (3886.42ms, 10.2MB)
테스트 2 〉	실패 (시간 초과)
테스트 3 〉	실패 (시간 초과)
테스트 4 〉	통과 (1738.99ms, 10.4MB)
테스트 5 〉	통과 (556.00ms, 10.3MB)
테스트 6 〉	통과 (220.40ms, 12.2MB)
테스트 7 〉	실패 (시간 초과)
테스트 8 〉	실패 (시간 초과)
테스트 9 〉	통과 (0.02ms, 10.2MB)

채점 결과

정확성: 55.6

합계: 55.6 / 100.0

 

아~ 실수~

def solution(distance, rocks, n):
    rocks.sort()
    start, end = 0, distance

    while start <= end :
        cnt = 0
        temp = distance
        current = 0
        mid = int((start+end)/2)
        for rock in rocks :
            dist = rock - current
            if dist >= mid : 
                temp = min(temp, dist)
                current = rock 
            else : 
                cnt += 1

        if cnt > n : end = mid - 1
        else : 
            answer = temp
            start = mid + 1
    return answer

정확성 테스트

테스트 1 〉	통과 (0.52ms, 10.3MB)
테스트 2 〉	통과 (0.45ms, 10.2MB)
테스트 3 〉	통과 (0.39ms, 10.2MB)
테스트 4 〉	통과 (16.79ms, 10.3MB)
테스트 5 〉	통과 (13.83ms, 10.4MB)
테스트 6 〉	통과 (127.86ms, 12.2MB)
테스트 7 〉	통과 (205.66ms, 12.2MB)
테스트 8 〉	통과 (193.28ms, 12.2MB)
테스트 9 〉	통과 (0.01ms, 10.3MB)

채점 결과

정확성: 100.0

합계: 100.0 / 100.0