(Python/LV3) 이중우선큐

문제 출처:https://school.programmers.co.kr/learn/courses/30/lessons/42628

프로그래머스

문제 풀이:

import heapq
def solution(operations):
    list = [] # heapq 만들예정 맨 위가 최솟값
    for i in operations:
        order, act = i.split(" ")
        if order == "I":
            heapq.heappush(list, int(act))
        else :
            if '-' in act: # - 가 붙으면 빼주는 것
                if len(list) == 0: # 근데 길이가 0 이면
                    pass    # 무시하고
                else:
                    heapq.heappop(list) # 길이가 0이 아니면 빼준다
            else: #최댓값을 삭제해줘야하는데 못함
                if len(list) == 0:
                    pass
                else:
                    list.remove(max(list))
                    heapq.heapify(list)
    return [max(list), min(list)] if len(list) >=2 else [0,0]

heapq 란 트리구조처럼 맨위에는 가장 작은수로 필두로 아래는 그것보다 작은거 2개 이다

위에 그림과 같은 형식이다 즉 맨위에가 최솟값이라는 소리 .. 어렵다면 밑에 문제를 풀고오자

https://windy7271.tistory.com/entry/PythonLV2-%EB%8D%94-%EB%A7%B5%EA%B2%8C

(Python/LV2) 더 맵게

3레벨이니 이제 풀이를 자세히 써봐야겠다

일단 list 를 만들어주고
입력값을 포문을 돌려서 order(명령) act(해야하는일) 로 변수를 만들었고

if order == "I":
    heapq.heappush(list, int(act))

만약 I 인 경우에 그냥 list에 넣어주면 되는데
heapq.heappush(리스트, 숫자) 이렇게 해주면 heapq 형식으로 만들어서 넣어준다 위에 그림 1,3,5,... 처럼

'-'가 붙은D 일경우는 최솟값을 빼주는거다

else :
    if '-' in act: # - 가 붙으면 빼주는 것
        if len(list) == 0: # 근데 길이가 0 이면
            pass    # 무시하고
        else:
            heapq.heappop(list) # 길이가 0이 아니면 빼준다

1. 최솟값을 빼야한다.
2. 뺄게 없으면 그냥 넘어간다 (pass)
3. 뺄게 있으면 heapq.heappop(list) 를 해주면 원래알던 pop 맨 뒤 요소를 빼는게 아닌 맨 앞요소(가장 최솟값)를 뺀다.

D일경우는 최댓값빼는경우

else: #최댓값을 삭제
    if len(list) == 0:
        pass
    else:
        list.remove(max(list))
        heapq.heapify(list)

1. 리스트가 빈거면 pass
2. 리스트에서 가장큰값을찾아 지우고 다시 heapq형으로 만든다
* heapify(리스트) heap형식으로 바꿔줌
뭔가 이 부분을 저렇게 안 바꾸고 하는 방법이 있을거같은데 생각해본다.



위 문제에서는
>> 맨아래 heapq.heapify(list) 를 빼줘도 된다 이유는 : pop이랑 push 할 때 재정렬이 된다
근데 pop과 push를 안거치고 연속적 최댓값을 빼줘야하는 상황이라면 안되는거같다
ex)

print(solution( ["I 6", "I 2", "I 1", "I 4", "I 5", "I 3", "D 1", "I 7", "D -1", "I 6", "D -1", "D -1"] ))
[7,4] 가 답이지만 맨 마지막줄을 빼면 [7,3] 이 나온다,

최종코드:

import heapq
def solution(operations):
    list = [] # heapq 만들예정 맨 위가 최솟값
    for i in operations:
        order, act = i.split(" ")
        if order == "I":
            heapq.heappush(list, int(act))
        else :
            if '-' in act: # - 가 붙으면 빼주는 것
                if len(list) == 0: # 근데 길이가 0 이면
                    pass    # 무시하고
                else:
                    heapq.heappop(list) # 길이가 0이 아니면 빼준다
            else: #최댓값 삭제
                if len(list) == 0:
                    pass
                else:
                    list.remove(max(list))
                    heapq.heapify(list)

    return [max(list), min(list)] if len(list) >=2 else [0,0]