(Hard) 다리를 지나는 트럭

개인적으로 시간을 낭비한 부분
1. 문제에서 최소 시간을 구하라고 해서 주이전 트럭 큐의 순서를 재정렬했다.;;
2. 1번에서 1시간정도 고민했는데, 출제의도상 내가 생각한 최소 시간의 의미가 달랐다
3. 마지막으로 테스트 케이스 시간초과 케이스가 나왔는데 timer pop 하는 부분에서 발생했다.
4. 질문하기를 보니, 무게 변동이 발생할때만 계산하라고 했는데 내 방식상 timer에서 전체 순회하는 부분이 원인으로 보였고, 이 부분을 0이 되면 삭제되게 바꾸었다.

import numpy as np

def solution(bridge_length, weight, truck_weights):

    waiting_queue = truck_weights

    # 이제 최단 시간을 만족하는 대기 큐 생성 완료
    # 그럼 시간을 구해야지
    current_weight = 0
    on_bridge = []
    time = 0
    timer = []
    while len(waiting_queue) !=0:
        if len(timer) != 0:
            # if on_bridge[0] != waiting_queue[0]:
            for i in range(len(timer)): # 다리위의 차량 잔존 운전시간 계산
                timer[i]= timer[i] - 1
                if timer[i] ==0:
                    on_bridge.pop(0)
                    # timer.remove(0)
                    current_weight = np.sum(on_bridge)
            try:
                timer.remove(0)
            except:
                pass

        if current_weight + waiting_queue[0] <= weight:
            # 조건 맞으니 차량 출발
            on_bridge.append(waiting_queue[0])
            # 다리에 올라간 순간, 내리는 시점을 계산해야함
            timer.append(bridge_length)
            
            current_weight = np.sum(on_bridge)
            waiting_queue.pop(0)
            
            time += 1

        else:
            # 조건 안맞으니 대기
            time += 1

        
    return time + int(np.max(timer)) 

주식 가격

문제 이해가 안되서 질문 글을 참조 :

문제의 의도는 떨어지기 전까지 몇 초나 버텼냐입니다. 떨어질 때를 기다렸다가 끝낸다. 즉, 무조건 손해 보고 판다는 개념이 이해가 안되고, 본능적으로 이해하려고도 하지 않는 겁니다. 주식해본 사람들은 제 말이 공감될 겁니다.

제한사항
prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
prices의 길이는 2 이상 100,000 이하입니다.
입출력 예
prices return
[1, 2, 3, 2, 3] [4, 3, 1, 1, 0]
입출력 예 설명
1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

내가 산 가격이 아닌 1초 뒤의 가격?
1초 시점의 가격이란 게 또 이해가 안됩니다.
주식을 해본 사람은 압니다. 내가 처음 산 가격이 중요한 거지 1초가 지난 시점의 가격이 중요한 게 아니죠.
그러니 이걸 1초가 지난 시점의 가격이 아닌 처음 산 시점(0초)으로 인식합니다.
그래서 5번이 지났으니 5초를 버텼다고 생각하는 게 자연스러운 데 여기선 이미 1초가 지난 시점에서 5초까지 버텼으니 5 - 1 = 4초를 버텼다고 보는 겁니다.
그렇다면 그걸 인정하고 가봅니다.

떨어지는 건 1초 봐준다?
그런데 3번째에서 이 문제의 의도와 다른 의도가 발생합니다.
3초 시점에서 4초 시점으로 갈 때 가격이 떨어집니다.
1번째에서 0이 아닌 1초가 지난 시점에서 시작했고 버틴 시간 중 0~1초는 인정을 하지 않습니다.
그런데 여기선 2~3초를 인정해서 1초간 버텼다고 인정해버립니다.
여기서 기준을 정하지 못해 멘붕이 옵니다.
한편 넣기였다가 갑자기 양편 넣기가 되버리니까요.
그리고 존버러의 논리로 돌아가기도 합니다.(제 경우)

역시 존버가 제일이야
3초 시점에서 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.란 설명이 있습니다.
이것은 3초 시점에서 3원이었다가 4초 시점에서 2원으로 떨어진 건 억울하지만, 5초 시점에서 다시 3원으로 복귀했다. 즉, 3~4초는 못 버텼지만 4~5초는 버텼으니 총 1초를 버틴 거라고 생각해 버립니다.
그래서 가장 왼쪽의 기준 가격과 오른쪽의 남은 가격들 중 기준 가격보다 낮은 가격들의 개수를 세는 실수를 하게 됩니다.
실제로는 버틴 시간만 세면 되니까 기준 가격보다 낮은 가격을 만나면 중단해 버려야 하는 데 말이죠.

def solution(prices):
    answer = [0] * len(prices)
    for i in range(len(prices)):
        for j in range(i+1, len(prices)):
            answer[i] += 1          
            if prices[j] < prices[i]:
                break

    return answer

스코빌 지수

힙큐 활용법을 배웠다.
결국 순서 상관없이 최소/최대값을 빠르게 알고 싶다면 힙큐를 활용한다.

import heapq

def solution(scoville, K):
    
    answer = 0
    flag = 0
    trial = 0
    heapq.heapify(scoville)
    
    heap_scov = scoville
    while 1:
        min_1st = heapq.heappop(heap_scov)
        # heap_scov 에 무조건 1개는 있다.
        try: # 그런데 2개가 없다면
            min_2nd = heapq.heappop(heap_scov)
        except:
            trial = -1
            break

        new_scov = min_1st + 2*min_2nd
        heapq.heappush(heap_scov, new_scov)

        trial += 1
        if heap_scov[0] >= K: # np.min(scovile) >= K :
            break

추가 활용법 :https://littlefoxdiary.tistory.com/3
기본 : import heapq
기본 : heapq.heapify(scoville)
힙에서 원소 삭제 : heappop
최대 힙 만들기

파이썬의 heapq 모듈은 최소 힙으로 구현되어 있기 때문에 
최대 힙 구현을 위해서는 트릭이 필요하다.

IDEA: y = -x 변환을 하면 최솟값 정렬이 최댓값 정렬로 바뀐다.

힙에 원소를 추가할 때 (-item, item)의 튜플 형태로 넣어주면 
튜플의 첫 번째 원소를 우선순위로 힙을 구성하게 된다.  
이때 원소 값의 부호를 바꿨기 때문에, 
최소 힙으로 구현된 heapq 모듈을 최대 힙 구현에 활용하게 되는 것이다.

아래의 예시는 리스트 heap_items에 있는 원소들을 max_heap이라는 최대 힙 자료구조로 만드는 코드이다.

heap_items = [1,3,5,7,9]

max_heap = []
for item in heap_items:
  heapq.heappush(max_heap, (-item, item))

print(max_heap)

heappush 함수를 통해 item을 힙에 push 할 때 (-item, item)의 튜플의 형태로 넣은 것을 확인할 수 있다.

 

그 결과 heappop을 사용하게 되면 
힙에 있는 최댓값이 반환되는 것을 확인할 수 있다. 
이때 실제 원소 값은 튜플의 두 번째 자리에 저장되어 있으므로 
[1] 인덱싱을 통해 접근하면 된다. 

max_item = heapq.heappop(max_heap)[1]
print(max_item)
```![](https://media.vlpt.us/images/soonwoo2003/post/9fca3102-5bda-4112-b3e8-ab7755b88ead/image.png)