https://school.programmers.co.kr/learn/courses/30/lessons/42891?language=python3
그냥 먹방을 하면 다른 방송과 차별성이 없기 때문에 무지는 아래와 같이 독특한 방식을 생각해냈다.
회전판에 먹어야 할 N 개의 음식이 있다.각 음식에는 1부터 N 까지 번호가 붙어있으며, 각 음식을 섭취하는데 일정 시간이 소요된다.무지는 다음과 같은 방법으로 음식을 섭취한다.
무지는 1번 음식부터 먹기 시작하며, 회전판은 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다 놓는다.
마지막 번호의 음식을 섭취한 후에는 회전판에 의해 다시 1번 음식이 무지 앞으로 온다.
무지는 음식 하나를 1초 동안 섭취한 후 남은 음식은 그대로 두고, 다음 음식을 섭취한다.다음 음식이란, 아직 남은 음식 중 다음으로 섭취해야 할 가장 가까운 번호의 음식을 말한다.
회전판이 다음 음식을 무지 앞으로 가져오는데 걸리는 시간은 없다고 가정한다.
무지가 먹방을 시작한 지 K 초 후에 네트워크 장애로 인해 방송이 잠시 중단되었다.무지는 네트워크 정상화 후 다시 방송을 이어갈 때, 몇 번 음식부터 섭취해야 하는지를 알고자 한다.각 음식을 모두 먹는데 필요한 시간이 담겨있는 배열 food_times, 네트워크 장애가 발생한 시간 K 초가 매개변수로 주어질 때 몇 번 음식부터 다시 섭취하면 되는지 return 하도록 solution 함수를 완성하라.
예시 food_times = [3,1,2], k = 5 0~1초: [2,1,2] 1~2초: [2,0,2] 2~3초: [2,0,1] 3~4초: [1,0,1] 4~5초: [1,0,0] 네트워크 에러 1번 음식부터 시작 result = 1
처음 드는 생각은 커서를 이용해서 문제를 풀어야 겠다.
1번에 커서를 두고 다음으로 이동하는데 0인지 체크하고 넘어가고
k초 뒤에 다음 커서를 구하면 되지 않을까?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def solution(food_times, k):
cur = 0
for i in range(k):
if (sum(food_times)!=0):
while(1):
if food_times[cur]!=0:
food_times[cur] = food_times[cur]-1
cur+=1
cur=cur%len(food_times)
break
cur+=1
cur=cur%len(food_times)
else:
return -1
return cur+1
결과는 엉망이었다 ㅋㅋ
내 생각의 흐름은 이렇게 돌아갔다. 일단 총 k 시간만큼 얼마나 먹었고 거기서 가까운 음식이 무엇인지 찾는 것이니
일단 k번 for문을 돌린다. 그리고 food_times가 0이라면 -1을 바로 반환을 하고 아니라면 적어도 남아 있는 음식이 1개는 있다는 의미이니 음식이 나올때까지 커서를 이동시키고 커서를 이동 시킬때마다 범위를 초과하지 않게 조절 한다였다.
그러면 뭐하나 잘못풀었다는 거 밖에 안되는데 ㅋㅋㅋ
해당 문제는 시간이 적게 걸리는 음식부터 확인하는 탐욕적인 접근 방법으로 해결할 수 있다. 모든 음식을 시간으로 정렬한 뒤에 시간이 적게 걸리는 음식부터 제거해 나가는 방식을 이용하면 된다. 이를 위해서 우선순위 큐를 사용하자
예시로 [8,6,4], k = 15가 있다고 가정하자
초기 단계에서는 모든 음식을 우선순위 큐(최소 합)에 삽입한다. 또한 마지막에는 K초 후에 먹어야 할 음식의 번호를 출력해야 하므로 우선순위 큐에 삽입할 때 (음식 시간, 음식 번호) 전체 남은 시간 15, 남은 음식 3
첫 단계에서는 가장 적게 걸리는 음식인 3번을 뺀다. 다만 음식이 3개 남아 있으므로 3(남은 음식의 개수) x 4(3번 음식을 먹는 시간) = 12를 빼야한다. 다시 말해 3번 음식을 다 먹기 위해서는 12초가 걸린다. 결과 적으로 전체 남은 시간은 15초에서 3초로 줄어들게 된다.
남은 시간은 3초이고 이번 단계에서는 두번째 음식을 빼야한다. 전체 음식이 두개 남아 있으므로 뺄 시간은 2(남은 음식의 개수) x 6(2번 음식을 다 먹는 시간) = 12초가 된다.
하지만 현재 남은 시간은 3초인데 12보다 작으므로 빼면 안된다.
따라서 다음으로 먹어야할 음식의 번호를 찾아서 출력하면 된다. 매초 먹어야할 음식을 나열해보자 남은 시간이 3초 이므로 4번째 음식을 출력하면 된다. 1(8) -> 2(6) -> 1(8) -> 2(6)
역시… 커서가지고 for문 돌리면서 난리를 쳤는데 우선순위 큐를 이용해서 해결한다.
코테를 볼때 개인적으로 for문의 사용을 최소화 해야하고 그러기 위해서는 스택이랑 우선순위 큐를 잘 사용해야하는데 손은 먼저 일단 이중삼중 for을 돌리고 있는게 문제….
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import heapq
def solution(food_times, k):
#전체 음식을 먹는 시간보다 k가 크거나 같다면 -1
if sum(food_times) <= k:
return -1
#시간이 작은 음식부터 빼야하므로 우선순위 큐를 사용
q = []
for i in range(len(food_times)):
#음식시간, 음식 번호 형태로 큐에 삽입
heapq.heappush(q, (food_times[i], i+1))
sum_value = 0 #먹기 위해 사용한 시간
previous = 0 #직전에 다 먹은 음식 시간
length = len(food_times) #남은 음식의 개수
#sum_value + (현재의 음식 시간 - 이전 음식 시간) * 현재 음식 개수와 k비교
while sum_value + ((q[0][0] - previous)*length) <= k:
now = heapq.heappop(q)[0]
sum_value += (now-previous)*length
length -= 1 #다먹은 음식 제외
previous = now #이전 음식 시간 재설정
#남은 음식 중에서 몇 번 째 음식인지 확인하여 출력
result = sorted(q,key=lambda x:x[1] ) #음식의 번호 기준으로 정렬
return result[(k-sum_value)%length][1]
코드로보면 위와 같다. 다시 보면
food_times의 합 /<= 시간 k일 경우에는 무조건 다 먹은뒤이니 -1을 먼저 리턴하고 아닐 경우에 아래로 넘어간다.
우선순위 큐를 위해서 q를 하나 만든다음 for문으로 넣어주는데 여기서는 for문과 range가 있지만 Python Effective에서는 for문을 돌릴때 index과 값이 동시에 필요하다면 enumerate을 사용하는게 간결성이 좋다고 합니다.
1
2
3
4
q=[]
for index,value in enumerate(food_times):
heapq.heappush(q, (index,value))
q
이렇게요 훨씬 보기 좋아졌지요?
그리고 heap에 넣을때 우선순위 큐라고 했는데 그냥 for문으로 넣지 따로 어떤 것을 사용하지 않는데 한번 찍어보면
이렇게 순서대로 8,6,4이 들어가게 됩니다. 그런데 힙에는 4-8-6순으로 들어가있네요
가장 작은 4가 0번(root)로 들어가있고 그리고 오른쪽/왼쪽 노드로 각 값이 들어가 있습니다. 여기서 4를 빼게된다면
이렇게 3번째에 있던 6이 처음으로 오게 됩니다. 최소 힙을 빼면 새로 자동으로 정렬합니다.
1
sum_value += (now-previous)*length
다시 돌아와서 일단 첫번째로 봅시다. 일단 먼저 빼진 것은 없으니 previous는 0이고 now는 4가 됩니다. 그리고 현재 음식의 길이는 3입니다. 즉 12가 빠지게 됩니다.
length -= 1 #다먹은 음식 제외 previous = now #이전 음식 시간 재설정 이렇게 음식이 하나가 빠지게 되고 앞서 4가 빠졌습니다.
1
2
#sum_value + (현재의 음식 시간 - 이전 음식 시간) * 현재 음식 개수와 k비교
while sum_value + ((q[0][0] - previous)*length) <= k:
두번째 while이 돌아가니 조건을 다시 확인해보면
q[0][0]에는 6이되고 앞서 4가 빠졌으니 2가 남고 길이 역시 2가 되니 총 4가 되고 앞서 소요한 시간 sum_value은 12
16/<=15가 되니 조건을 만족하지 않아 마지막으로 갑니다.
1
result = sorted(q,key=lambda x:x[1] ) #음식의 번호 기준으로 정렬
q에서 분명 6, 8 순서로 들어 있는데 sorted에서 x/[1/]/(인덱스/) 기준으로 새로 정렬을 하면 result가 만들어집니다.
남은 것은 3이고 이를 2(길이)로 나눈 나머지는 1
정답은 1이 나오게 됩니다.
Comments powered by Disqus.