문제 출처: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
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]
댓글