[20210701] (프로그래머스) 무지의 먹방 라이브
프로그래머스 4단계 무지의 먹방 라이브를 풀이한다.
개인적인 얘기를 먼저 해보자면, 프로그래머스 4단계를 처음 풀어보았다. 생각보다 쉽게 풀렸던 것 같아서 내가 실력이 늘어서 인지 운이 좋았던 건지 모르겠지만, 4단계를 풀었다는 것에 기분이 좋아졌었지만 그래프 공부를 하면서 다시 뇌가 일을 하지 않기 시작했다…
이제 풀이를 시작하겠습니다!
문제
https://programmers.co.kr/learn/courses/30/lessons/42891
짧게 요약을 해보자면 무지가 회전판에 올려진 음식들을 차례대로 한 입씩 먹어 나가다가 통신 문제로 방송이 중단되고, 방송을 다시 시작한 후에 다시 먹기 시작해야하는 음식을 찾는 문제이다.
첫번째 풀이
첫 풀이라기 보다는 처음 생각했을 때, Queue를 이용해서 모든 음식을 회전판에 놓인 순서대로 Queue에 저장하고 하나씩 꺼내서 한 입 먹고 음식이 남으면 Queue에 다시 저장하는 방식으로 풀면 효율성은 만족하지 못하더라도 정확성은 쉽게 넘길 수 있을 것 같았다.
Queue로 풀게되면 시간복잡도를 구해보자. 회전판에 놓인 음식의 갯수가 n이고, k가 방송이 중단된 시간이라고 하자. 그러면 회전판을 한 바퀴 도는 동안 먹는 시간복잡도가 O(n) 방송 중에 회전판이 돈 횟수 O(k / n) 으로 Queue를 이용한 풀이는 O(n) * O(k / n)이 된다.
두번째 풀이
Queue를 이용한 시간복잡도에서 복잡도를 줄일만한 아이디어를 생각하다가 회전판에 놓인 음식을 안 셀 수는 없다 생각이 들었다. 그래서 회전판을 매번 돌리지않고 횟수를 구할 수 없을까 라는 생각이 들었다. 그래서 사용하게 된 것이 binarySearch이다. 방송 동안에 회전판을 돌린 횟수를 알 수 있다면, 이제껏 먹었던 음식들의 양을 알 수 있고, 이제 먹어야 하는 음식의 양도 알 수 있다. 그래서 방송 동안 회전판을 돌링 횟수를 binarySearch로 구하여 답을 구할 수 있었다.
binarySearch로 풀면 시간복잡도는 O(n) * O(log(k / n))이 된다.