김낭만

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

백준(BOJ) 19591 독특한 계산기 파이썬(Python)

문제 링크

20129번 뒤집힌 계산기와 유사한 문제.
비슷한 방식으로 풀 수 있는데, 연산자, 피연산자 파싱은 유사한 방법으로 진행하면 된다.
첫 피연산자가 음수일 수 있는데, 이 부분만 예외처리를 해주면 된다.
이후에는 앞, 뒤에서만 연산이 일어난다는 점에 착안해 데크를 이용해 주어진 조건에 따라 계산을 해주면 된다.
연산자 데크가 비고 피연산자 데크에 원소가 하나만 남는다면 계산이 완료된 것이다.
20129번과 마찬가지로 C(C++) 나눗셈 연산은 int(a / b)로 구현할 수 있다.

#!python

from re import split
from collections import deque

# a op b의 결과를 반환한다
# C(C++) 나눗셈을 위해 나눗셈은 int(a / b)로 계산된다
def calc(a, b, op):
    if op == '+':
        return a + b
    if op == '-':
        return a - b
    if op == '*':
        return a * b
    return int(a / b)

exp = input()
# flag는 맨 첫 숫자가 음수인지를 확인
flag = False

# 만약 첫 숫자가 음수면 flag를 True로 하고 -를 잘라냄
if exp[0] == '-':
    exp = exp[1:]
    flag = True

# re.split()으로 정수 분리하여 데크에 넣는다
operands = deque(map(int, split('[+\-*/]', exp)))
operators = deque()

# flag가 참이라면 -로 시작하므로 0번 피연산자에 -를 넣는다
if flag:
    operands[0] = -operands[0]

# 표현식을 순회하면서 연산자를 분리하는 코드
for e in exp:
    if e in ('+', '-', '/', '*'):
        operators.append(e)

# 연산자 데크가 빌 때까지
# 계산이 완료되면 연산자 데크는 비고 피연산자 데크는 원소가 하나 남음
while operators:
    # l은 왼쪽 계산결과 r은 오른쪽 계산결과
    l = calc(operands[0], operands[1], operators[0])
    r = calc(operands[-2], operands[-1], operators[-1])
    # 왼쪽이 곱셈, 나눗셈이고 오른쪽이 덧셈, 뺄셈인 경우
    if operators[0] in ('*', '/') and operators[-1] in ('+', '-'):
        operators.popleft(); operands.popleft(); operands.popleft()
        operands.appendleft(l)
    # 왼쪽이 덧셈, 뺄셈이고 오른쪽이 곱셈, 나눗셈인 경우
    elif operators[-1] in ('*', '/') and operators[0] in ('+', '-'):
        operators.pop(); operands.pop(); operands.pop()
        operands.append(r)
    # 우선순위가 같고 왼쪽이 오른쪽 이상인 경우
    elif l >= r:
        operators.popleft(); operands.popleft(); operands.popleft()
        operands.appendleft(l)
    # 우선순위가 같고 오른쪽이 왼쪽보다 큰 경우
    else:
        operators.pop(); operands.pop(); operands.pop()
        operands.append(r)

print(operands[0])

2024

맨 위로 이동 ↑

2023

세그먼트 트리

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

벨만-포드 알고리즘

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

다익스트라 알고리즘

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

맨 위로 이동 ↑