처음에 아무 생각 없이 while문 돌려서 stones 모든 Inde에 -1씩 해주고 k번 이상 뛰어넘게 되면 while문 탈출해서 답을 구하도록 짰는데, 역시나 효율성 테스트에서 통과하지 못했다.
한 번 통과 못하니까 바로 이진 탐색 써야겠다는 생각이 들었다..
def solution(stones, k):
answer = 0
"""
k칸을 뛰어넘지 않는 한도에서 최솟값을 이진탐색으로 구하자
left는 1로, right는 max 함수 써서 구하니까 더 빠르게 구해졌다.
"""
left = 1
right = max(stones)
while left <= right:
mid = (right+left) // 2
cnt = 0
for i in range(len(stones)):
if stones[i] - mid <= 0:
cnt += 1
else:
cnt = 0
if cnt >= k:
break
if cnt >= k:
right = mid - 1
answer = mid
else:
left = mid + 1
return answer
채점 결과
정확성 테스트
테스트 1 〉 통과 (0.01ms, 10.2MB)
테스트 2 〉 통과 (0.01ms, 9.91MB)
테스트 3 〉 통과 (0.02ms, 9.99MB)
테스트 4 〉 통과 (0.02ms, 10MB)
테스트 5 〉 통과 (0.02ms, 10.4MB)
테스트 6 〉 통과 (0.32ms, 10.4MB)
테스트 7 〉 통과 (0.78ms, 9.91MB)
테스트 8 〉 통과 (0.78ms, 10.3MB)
테스트 9 〉 통과 (0.80ms, 10.1MB)
테스트 10 〉 통과 (0.03ms, 10.4MB)
테스트 11 〉 통과 (0.01ms, 10.3MB)
테스트 12 〉 통과 (0.02ms, 10.2MB)
테스트 13 〉 통과 (0.04ms, 10.2MB)
테스트 14 〉 통과 (0.49ms, 10.1MB)
테스트 15 〉 통과 (0.86ms, 10MB)
테스트 16 〉 통과 (0.56ms, 10.4MB)
테스트 17 〉 통과 (1.25ms, 10.2MB)
테스트 18 〉 통과 (0.01ms, 10.4MB)
테스트 19 〉 통과 (0.03ms, 10.2MB)
테스트 20 〉 통과 (0.06ms, 10.2MB)
테스트 21 〉 통과 (0.56ms, 10.2MB)
테스트 22 〉 통과 (0.85ms, 10.3MB)
테스트 23 〉 통과 (0.79ms, 10.4MB)
테스트 24 〉 통과 (0.80ms, 10.2MB)
테스트 25 〉 통과 (0.01ms, 10.2MB)효율성 테스트
테스트 1 〉 통과 (371.63ms, 18.5MB)
테스트 2 〉 통과 (408.08ms, 18.5MB)
테스트 3 〉 통과 (443.08ms, 18.5MB)
테스트 4 〉 통과 (293.90ms, 18.6MB)
테스트 5 〉 통과 (311.59ms, 18.5MB)
테스트 6 〉 통과 (353.97ms, 18.6MB)
테스트 7 〉 통과 (477.72ms, 18.5MB)
테스트 8 〉 통과 (496.83ms, 18.5MB)
테스트 9 〉 통과 (444.19ms, 18.5MB)
테스트 10 〉 통과 (484.84ms, 18.6MB)
테스트 11 〉 통과 (414.82ms, 18.6MB)
테스트 12 〉 통과 (480.35ms, 18.5MB)
테스트 13 〉 통과 (355.21ms, 18.5MB)
테스트 14 〉 통과 (245.50ms, 18.6MB)
채점 결과
정확성: 64.1
효율성: 35.9
합계: 100.0 / 100.0
이진탐색으로 풀어야겠다고 생각이 들면 그렇게까지 어려운 문제는 아닌 것 같다.
단지.. 처음에 left
right
설정 부분이 조금 중요했는데,
left = min(stones)
right = max(stones)
으로 지정했을 때 효율성 테스트
8번에서 시간 초과가 일어났고,
left = 1
right = max(stones)
#혹은 right = 200000000
로 수정했을 때 정상적으로 모두 통과가 됐다.
min()
max()
함수는 전체를 다 돌면서 최소, 최댓값을 구해야하기 때문에 시간복잡도가 O(N)
이다.
그래서 효율성을 요구하는 문제에는 신중하게 사용해야한다!
(사용하지 않을 수 있으면 그러는게 좋음)