링크

도둑질

난이도

  • 프로그래머스 난이도 4, 이분법이라는 키워드를 떠올리면 빨리 풀린다.
    • 효율성이라 이분법 해봤는데 됐다!(음..)

문제요약

  • 무지가 무지막지하게 먹는다.(켄스케군 그러면안돼! [퍽])
  • 돌아가는테이블로 순서대로 1초마다 먹방시작, k초가 주어질때 몇번째 음식을 먹어야 할까?

접근

  • 이분법
    • 제공된 숫자가 너무 크다보니 이분법을 먼저 적용해보았다.

간단 알고리즘

  • 음식들은 food_times, 주어진 k초
  • 예외
    • 모든 음식들 더하기sum(food_times) <= k이면 더이상 먹을게 없어졌다는 의미로 return -1
  • 무엇을 이분법을할지 정하기
    • 모든 음식에 공통적으로 먹어야 하는 갯수를 이분법으로 찾는다.
    • left = 1, right = max(food_times), mid = (left+right)//2
      • 먹는 음식 sumCheck
      • 모든 food_times에 mid를 빼준다.
        • 각 음식시가 f<=mid면 sumCheck+=f
        • f>mid , sumCheck+=mid
    • sumCheck<=k 는 left = mid+1
    • sumCheck>k 는 right = mid-1
    • 이렇게 하면 right로 딱 모든 음식들을 공통적으로 먹이는 갯수가 나온다.
    • righrt를 다시 모든 음식을 먹인다.
      • k -=sumCheck를 해서 남은 시간을 계산
    • 다시 food_times돌면서 0이아닐때 k-=1, k==0이면 해당 index를 정답으로!

후기

  • 이분법을 알고 적용하니 잘 풀린듯하다.
  • 좀 반복이 여러번 되긴했는데 괜찮은가보다