728x90
https://school.programmers.co.kr/learn/courses/30/lessons/340212?language=python3
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
이 문제는 diff와 level을 비교해서
level < diff일 경우와 level >= diff일 경우로 나눠서 진행합니다.
level < diff인 경우 (time_cur + time_prev) * (diff - level) + time_cur 만큼의 시간 소요
level >= diff인 경우 time_cur 만큼의 시간 소요
이 때 limit 시간 안에 해결할 수 있는 level을 찾으면 되는데요.
저는 처음에 반복문으로 1부터 max(diff)까지 순차적으로 확인했습니다.
방법1. 반복문 사용
def solution(diff, time, limit):
m = max(diff)
for level in range(1, m+1):
answer = 0
for i in range(len(time)):
if level < diff[i]:
answer += (time[i]+time[i-1])*(diff[i]-level) + time[i]
else:
answer += time[i]
if answer > limit:
break
if answer <= limit:
return level
결과는 당연히 시간 초과로 실패였습니다.
어떤 방식을 써야할 지 고민하다가 for문으로 순차적 확인 대신 이진 탐색을 해야겠다는 생각을 했습니다.
방법2. 이진 탐색 사용
def bs(start, end, diff, time, limit):
if start > end:
return end+1
level = (start+end)//2
answer = 0
for i in range(len(time)):
if level < diff[i]:
answer += (time[i]+time[i-1])*(diff[i]-level) + time[i]
else:
answer += time[i]
if answer <= limit:
return bs(start, level-1, diff, time, limit) # level 최솟값을 찾기 위해 왼쪽으로
else:
# answer > limit
return bs(level+1, end, diff, time, limit) # level을 더 증가시키기 위해 오른쪽으로
def solution(diff, time, limit):
m = max(diff)
res = bs(1, m, diff, time, limit)
return res
tc 13이 5초가 넘게 걸렸는데, 이진 탐색으로 0.003초가 걸렸습니다.
이제 순차적으로 탐색하는 문제가 나오는데 숫자가 굉장히 많다면 이진 탐색을 사용하는 것으로!!
'코딩테스트 문제' 카테고리의 다른 글
[백준/Python] 곱셈 (0) | 2025.02.09 |
---|---|
[백준/Python] LCS (0) | 2025.01.19 |
[Python] 반복문으로 dfs 구현하기 (0) | 2025.01.14 |
[백준/Python] 동물원 (0) | 2024.10.29 |
[백준/Python] 이진 검색 트리 (1) | 2024.10.17 |