아래 프로그래머스 로고를 클릭하면 해당 문제로 이동합니다 😀
풀이과정
일단 이진 탐색 binary search를 생각했다.
숙련도로 가질 수 있는 값은 diff의 min과 max 사이가 될테니 그 사이에서 가질 수 있는 값을 level_arr에 쭉 만들었고, pivot을 가운데 값으로 설정했다.
그리고 나서 이진탐색을 시작하는데 이때 solve_puzzle라는 함수를 만들어서 소요시간을 계산하게 했다.
위 함수는 문제에서 주어진 대로 코드를 작성했다.
그리고 나서 함수에서 리턴된 소요시간을 limit와 비교했을때,
-
limit보다 크면 숙련도가 더 낮아져야 한다는 의미와 같으므로
end = pivot-1을 -
limit보다 작으면
levelable에 저장한 후 레벨을 높였을 때 가능한 케이스가 있는지 확인한다.
그리고 마지막으로 levelable에서 가장 작은 값을 뽑아서 리턴해주면 된다.
코드
def solve_puzzle(level, diffs, times):
solve_time = 0
for i in range(len(diffs)):
if diffs[i] <= level:
solve_time += times[i]
else:
solve_time += (diffs[i] - level) * (times[i] + times[i-1]) + times[i]
return solve_time
def solution(diffs, times, limit):
level_arr = [i for i in range(min(diffs), max(diffs)+1)]
start, end = 0, len(level_arr)-1
levelable = []
while start <= end:
pivot = (start + end) // 2
if solve_puzzle(level_arr[pivot], diffs, times) <= limit:
levelable.append(level_arr[pivot])
end = pivot - 1
else:
start = pivot + 1
answer = min(levelable)
return answer결과
