김낭만

재밌거나 필요하다고 생각하는 걸 만듭니다.

백준(BOJ) 16228 GCC의 유산 파이썬(Python)

문제 링크

수식 계산 문제.
교과서적인 문제.
연산자에 우선순위가 있고 식에 괄호가 존재하므로 후위표기법을 사용하면 된다.
수식을 파싱하면서 후위표기법으로 변환하고(이때 피연산자 파싱에 유의하자), 후위표기법으로 변환된 수식을 계산하면 된다.
>?와 <? 같은 경우는 그냥 min(), max() 연산이고, 2글자짜리 심볼이지만 그냥 <와 >여도 구분이 가므로(즉, ?는 그냥 무시하고 넘어가면 되므로) 크게 상관은 없다.
피연산자 파싱은 문자열을 이어붙이는 게 오래걸릴 수 있으므로(사실 입력이 작아서 아무래도 좋다) + 연산자로 연결하는 대신 인덱스를 저장해뒀다가 한번에 슬라이싱했다.
그 외에는 크게 어려울 것은 없는 문제.

#!python

exp = input()
l = len(exp)
# 후위표기법 변환을 위한 우선순위 매핑
prio = {'(': 0, ')': 0, '+': 1, '-': 1, '>': 2, '<': 2}
stack = []
# 후위표기법 수식을 담을 리스트
postfix = []

# t는 피연산자의 시작 인덱스
t = 0
for i, e in enumerate(exp):
    # e가 숫자고, 다음 심볼이 숫자가 아니거나 수식이 끝났으면 피연산자이므로 postfix에 담음
    if e in map(str, range(10)):
        if i + 1 == l or exp[i+1] not in map(str, range(10)):
            postfix.append(exp[t:i+1])
        continue
    # e가 연산자면 후위표기법 변환 규칙에 따라 우선순위를 비교
    if e in '+-<>':
        while stack and prio[e] <= prio[stack[-1]]:
            postfix.append(stack.pop())
        stack.append(e)
    # e가 여는 괄호면 무조건 스택에 추가
    elif e == '(':
        stack.append(e)
    # e가 닫는 괄호면 여는 괄호가 나올 때까지 팝
    elif e in ')':
        while True:
            p = stack.pop()
            if p == '(':
                break
            postfix.append(p)
    # 여기까지 왔으면 연산자라는 뜻이므로 연산자 다음 기호는 피연산자이다
    t = i + 1
# 스택에 남은 연산자 추가
postfix.extend(reversed(stack))

# 후위표기법 계산
stack = []
for e in postfix:
    # 연산자면 2개를 팝해서 계산 후 스택에 넣기
    if e in '+-<>':
        b = stack.pop()
        a = stack.pop()
        if e == '+':
            stack.append(a + b)
        elif e == '-':
            stack.append(a - b)
        elif e == '<':
            stack.append(min(a, b))
        else:
            stack.append(max(a, b))
    # 피연산자면 그냥 스택에 추가
    else:
        stack.append(int(e))

# 마지막에 스택에 남은 숫자 출력
print(stack[0])

2024

맨 위로 이동 ↑

2023

세그먼트 트리

개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...

벨만-포드 알고리즘

개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...

다익스트라 알고리즘

개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...

맨 위로 이동 ↑