- 백준 11286 절댓값 힙
풀이
n = int(input())
q1 = [] # 음수를 넣을 큐
q2 = [] # 양수를 넣을 큐
for i in range(n):
a = int(sys.stdin.readline())
if a < 0:
heapq.heappush(q1, -a) # 절대값이 가장 작은 값을 출력할 예정이므로, 즉 절대값이 기준이 되므로, 음수를 양수로 바꾸어 넣어준다.
elif a > 0:
heapq.heappush(q2, a) # 양수이므로 그대로 넣어준다.
else:
if not q1: # q1이 비어있는 경우
if not q2: # q1, q2 모두 비어있는 경우
print(0) # 배열이 아예 비어있으므로 0 출력
else: # q1만 비어있는 경우
print(heapq.heappop(q2)) # heapq.heappop : heap에서 가장 작은 원소를 pop & 리턴 / q1이 비어있으므로 q2에서 가장 작은 원소를 pop&리턴
elif not q2: # q2만 비어있는 경우
print(-heapq.heappop(q1)) # q2가 비어있으므로 q1에서 가장 작은 워소를 pop&리턴. 리턴시 -를 붙인다. (q1에는 절댓값이 입력된 상태이다. 문제에서 요구하는 것은 절댓값 출력이 아닌 원래의 수 출력이다.)
else: # q1, q2 모두 차있는 경우
tmp1 = -heapq.heappop(q1) # q1에서 가장 작은 원소를 pop&리턴. 리턴시 -를 붙인다.
tmp2 = heapq.heappop(q2) # q2에서 가장 작은 원소를 pop&리턴
if abs(tmp1) > abs(tmp2): # 절대값 비교.
print(tmp2) # 작은 절대값 출력
heapq.heappush(q1, -tmp1) # q1의 원소는 제거할 필요가 없으므로 다시 넣어준다.
else:
print(tmp1) # 작은 절대값 혹은 동일한 절대값 출력
heapq.heappush(q2, tmp2) # q2의 원소는 제거할 필요가 없으므로 다시 넣어준다. - (중요) heapq.heappop(큐): 큐에서 가장 작은 원소를 pop & 리턴
- 백준 9012 괄호
풀이
import sys
input = sys.stdin.readline
T = int(input())
for i in range(T):
stack = []
a=input()
for j in a:
if j == '(':
stack.append(j) # j가 ( 라면 스택에 넣어준다
elif j == ')':
if stack: # j가 ) 일 때 스택 안에 문자가 존재한다면,
stack.pop() # 스택 맨 뒤의 요소를 빼준다.
else: # 스택이 비어있으면
print("NO") # )에 대응되는 (가 없다는 소리이므로 "NO"를 출력한다.
break # 반복문 탈출
else: # for 문에서 한번도 break가 난 적이 없다면 else문을 실행한다.
if not stack: # break으로 끊기지 않고 스무스하게 스택이 비게 되면 정상적인 괄호인 거라 판별할 수 있다.
print("YES")
else:
# 요게 중요한데, break가 안 걸렸다 하더라도 스택에 괄호가 들어있을 수 있다. 하지만 이 경우는 for 문을 다 돌았음에도 불구하고, 즉 입력한 문자열에 존재하는 모든 )와 대응되는 (를 전부 제거했음에도 불구하고 스택이 비지 않은 것이므로 입력한 문자열이 정상적인 괄호가 아닌 것이다.
print("NO")
# for - else 문: 보통 else 는 if와 많이 쓰지만 파이썬에서는 for문과 쓰이기도 한다. 이 경우, for문이 break 등으로 끊기지 않고 끝까지 수행되었을 때 else문을 실행한다.- 이 문제의 키 포인트는 주어진 문자열 순서대로 대응시킬때 )에 대응되는 (가 없다면 정상적인 괄호가 아니라는 것이다.
- for-else 문: for 문이 break 등으로 끊기지 않고 끝까지 수행되었을 때, else 문을 실행한다.
- 대응 과정을 다 끝냈는데도 불구하고 스택이 비지 않았다면 정상적인 괄호가 아니라는 뜻이다.
출처
정지호