문제출처
https://school.programmers.co.kr/learn/courses/30/lessons/64062
문제를 스스로 해결하였는가? -> O
이분탐색 아이디어를 떠올리기까지 그리 오래 걸리지 않았다. 하지만 효율성 검사를 통과하기가 꽤나 까다로웠다. 초기에 작성한 실패코드와 성공코드를 같이 놓고 어떤 차이가 있었는지 비교하자.
사용된 알고리즘
- 이분탐색
실패 코드
def solution(stones, k):
left, right = 0, max(stones)
while left <= right:
mid = (left+right)//2
cnt, maxi = 0, 0
for stone in stones+[mid]:
if stone < mid:
cnt += 1
else:
maxi = max(cnt, maxi)
cnt = 0
if maxi >= k:
right = mid-1
break
if maxi < k:
left = mid+1
return right
정확성 테스트에선 통과됐으나 효율성 13번에서 시간초과가 발생한 코드다. 반복문 내에서 max함수를 계속해서 사용했던게 문제였던 것 같다.
성공 코드
def solution(stones, k):
left, right = 0, max(stones)
while left <= right:
mid = (left+right)//2
cnt, maxi,flag = 0, 0, True
for stone in stones:
if stone < mid:
cnt += 1
else:
cnt = 0
if cnt >= k:
right = mid-1
flag = False
break
if flag:
left = mid+1
return right
flag 변수를 사용해 반복문마다 불필요한 max 함수 사용을 제거했더니 통과됐다.
'알고리즘 (Python) > 프로그래머스' 카테고리의 다른 글
[프로그래머스][Level2] 구명보트 (파이썬) (0) | 2022.08.13 |
---|---|
[프로그래머스][Level2] 조이스틱 (파이썬) (0) | 2022.08.13 |
[프로그래머스][Level2] 다리를 지나는 트럭 (파이썬) (0) | 2022.08.13 |
[프로그래머스][Level2] 양궁대회 (파이썬) (0) | 2022.08.13 |
댓글