[백준]230215-16 문제풀이

1946. 신입사원

import heapq
import sys

T = int(input())
for i in range(T):
    N = int(sys.stdin.readline())
    heap = []
    pass_list = []
    for j in range(N):
        a, b = map(int, input().split())
        heapq.heappush(heap, (a,b))
    pass_list.append(heapq.heappop(heap))
    while heap:
        a = heapq.heappop(heap)
        if a[1] < pass_list[-1][1]:
            pass_list.append(a)
    print(len(pass_list))

대충 로직 맞는데 시간초과 떠서 pypy로 제출해버렸다. 힙에는 주로 배열 형태를 집어넣게 되는 것 같다.

1918. 후위 표기식

lst = list(input())
priority = {'(': 0, '+': 1, '-': 1, '*': 2, '/': 2}
stack = []
result = ''

while lst:
    temp = lst.pop(0)
    if temp.isalpha():
        result += temp
    elif temp == ')':
        while stack and stack[-1] != '(':
            result += stack.pop()
        stack.pop()
    elif temp == '(':
        stack.append(temp)
    else:
        if stack:
            while priority[stack[-1]] >= priority[temp]:
                result += stack.pop()
                if not stack:
                    break
            stack.append(temp)
        else:
            stack.append(temp)

while stack:
    result += stack.pop()
print(result)

이틀동안 사람 정신나가게 만든 문제. 결국엔 코드 보고 베꼈는데, 아무리봐도 원리는 이해 안되고 하라는대로 구현해도 아직 실력이 안되는지 계속 반례가 하나씩 생겼다. 나중에 실력이 좀 탄탄해지면 꼭 다시 도전해볼 문제.