백준 11497 통나무 건너뛰기

import sys
input = sys.stdin.readline
from collections import deque
from heapq import heappush, heappop, heapify

max = 0
num = int(input())
heap = []
for i in range(num):
    length = int(input())
    temp = list(map(int, input().split(" ")))
    for j in range(length):
        heappush(heap, -temp[j])
        
    q = deque()
    for k in range(length):
        if(k % 2 == 0):
            q.append(heappop(heap))
        else:
            q.appendleft(heappop(heap))
            
    max = 0
    for h in range(length-1):
        if(abs(q[h]-q[h+1]) > max):
            max = abs(q[h]-q[h+1])
    if(q[0]- q[length-1] > max):
        max = abs(q[0]-q[length-1])
    print(max)
        
    

처음 문제를 풀 때 파이썬 내에서 힙이라는 자료구조만 알고 있던 터라 표현에 어려움을 겪었다 하지만 덱이라는 자료구조가 존재한다!!!

1. deque

덱은 몹시 빠르다고 한다 정확하게는 O(1)
덱은 스택으로도 큐로도 사용이 가능하다

from collections import deque

temp = deque() #deque 선언
temp.append(22)
temp.appendleft(12) #왼쪽에서도 삽입이 가능하다!

temp.pop()
temp.popleft() #제일 좌측의 값 반환 및 삭제

temp.remove(22) #특정 값 삭제

temp.extend(array)
temp.extendleft(array) #리스트 속의 값 추가 0번째 부터 차례대로

temp.rotate(2) #양수 -> 시계 방향 / 음수 -> 반시계 방향 

일단 방향 측면에서 자유롭다는 점이 리스트와의 도드라지는 차이점인 것 같다.
또한 rotate라는 함수는 처음보는데 원형연결 리스트 느낌으로 돌아간다 생각하면 편할 것 같다.

2. 힙 다시

from heapq import heappush, heappop

temp = [] # 빈 리스트를 작성한 후

heappush(temp, 22) #힙에 22, 37 넣기
heappush(temp, 37)

print(heappop(temp))

print(temp[0]) #특이한 점이다! 힙의 0번째 인덱스는 항상 최소값을 지닌다

위의 코드는 min heap을 구현하는 방법이고

max heap을 구현하기 위해서는 음수를 붙인채 저장을 하고 출력할때도 마이너스를 붙여 출력하는 방식을 취한다

from heapq import heappop. heappush
max_heap = []

heappush(max_heap, -22) #실제 넣고 싶은 값은 22, 37 
heappush(max_heap, -37)

print(-heappop(max_heap)) #출력할때도 마이너스를 붙여서