김낭만

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

백준(BOJ) 20129 뒤집힌 계산기 파이썬(Python)

문제 링크

수식을 파싱하고 주어진 방법대로 계산해야 하는 문제.
19591 독특한 계산기의 변종 문제라고 하는데, 안 풀어봐서 모르겠으나 얼핏 봐도 비슷하기는 하다.
먼저 연산자 우선순위를 정해진 대로 설정해야 하는데, 높은 숫자가 높은 우선순위를 가지니 리스트에 저장해 순서대로 계산하는 방식을 사용했다.
파싱은 주어진 식을 순회하며 연산자와 피연산자를 분리해주면 된다.
처음에는 한 번 순회하며 피연산자를 문자열로 저장하다가 연산자가 나타나면 지금까지 저장한 피연산자를 리스트에 플러쉬하는 방식으로 하려고 했는데, 불변 객체인 문자열 연결을 반복하면 느릴 수 있겠다는 생각이 들어 re.split()을 이용해서 분리했다.
실제로 살펴보면 re.split()은 _sre.c 안에 슬라이싱을 통해 구현된 것으로 보이는데, 그러므로 확실히 더 빠를 것이다(그런데 다른 풀이를 봤더니 그냥 더한 풀이도 많은 거 봐선 괜히 한 듯..).
이후 각 연산자를 계산하기 위해 식을 총 4번 순회해주었다.
여기서 계산 결과를 저장하기 위해 유니온 파인드를 활용했는데, 풀이를 보니 스택이나 데크를 활용한 풀이도 있더라.
스택을 이용한 풀이가 아마 정석이고 가장 빠를 것이라 생각한다.
아무튼, 각 피연산자를 노드로 놓고 계산이 된 피연산자끼리 유니온해주면 된다.
모든 연산자에 대해 계산을 완료하면 피연산자들이 하나로 유니온되었을 것이니 답을 출력해주면 된다.
참고로, 파이썬과 C(또는 C++)는 음수 나눗셈이 다른 방식으로 되는데, int(a/b)를 하면 C와 같은 답이 나온다.

#!python

from re import split

# 유니온 파인드
def root(node):
    if parent[node] != node:
        parent[node] = root(parent[node])
    return parent[node]

def union(a, b):
    ra, rb = root(a), root(b)
    parent[ra] = parent[rb] = min(ra, rb)

# 연산자 우선순위 입력
p = map(int, input().split())
# 4개의 연산자
ops = '+', '-', '*', '/'
# 연산자의 우선순위 순서대로 저장
prio = ['' for _ in range(4)]
for i, e in enumerate(p):
    prio[4-e] = ops[i]

# 수식 입력
exp = input()

# 피연산자는 re.split()을 이용해서 분리 후 뒤집기
operands = list(map(int, split(r'[+\-*/]', exp)))
operands.reverse()
# 연산자는 수식을 순회하며 넣음
operators = []
for e in exp:
    if e in ops:
        operators.append(e)

# 유니온 파인드를 위한 리스트
parent = list(range(len(operands)))

# 연산자가 4개이므로 우선순위대로 4번 반복
for e in prio:
    # 뒤에서부터 시작
    for i, op in enumerate(reversed(operators)):
        # 현재 우선순위의 식인 경우
        if op != e:
            continue
        # 파인드로 두 루트 노드의 값을 계산해서 저정한다
        # 이후 두 피연산자가 하나로 계산되었으므로 유니온한다
        if op == '+':
            operands[root(i)] = operands[root(i + 1)] = operands[root(i)] + operands[root(i + 1)]
            union(i, i + 1)
        if op == '-':
            operands[root(i)] = operands[root(i + 1)] = operands[root(i)] - operands[root(i + 1)]
            union(i, i + 1)
        if op == '*':
            operands[root(i)] = operands[root(i + 1)] = operands[root(i)] * operands[root(i + 1)]
            union(i, i + 1)
        if op == '/':
            # 파이썬에서 C++ 방식(C언어 방식) 나눗셈은 int(a/b)로 구현할 수 있다
            operands[root(i)] = operands[root(i + 1)] = int(operands[root(i)] / operands[root(i + 1)])
            union(i, i + 1)
# 연산을 모두 끝내면 모든 노드가 하나로 유니온되어 있다
# 사실 그러면 빠른 노드가 루트가 되므로 0이 루트겠지만...
print(operands[root(0)])

2024

맨 위로 이동 ↑

2023

세그먼트 트리

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

벨만-포드 알고리즘

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

다익스트라 알고리즘

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

맨 위로 이동 ↑