그냥 코딩하는 사람의 블로그

문제 설명

문제

후위 표기식과 각 피연산자에 대응하는 값들이 주어져 있을 때, 그 식을 계산하는 프로그램을 작성하시오.

입력

첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이는 100을 넘지 않는다) 그리고 셋째 줄부터 N+2번째 줄까지는 각 피연산자에 대응하는 값이 주어진다. 3번째 줄에는 A에 해당하는 값, 4번째 줄에는 B에 해당하는값 , 5번째 줄에는 C ...이 주어진다, 그리고 피연산자에 대응 하는 값은 100보다 작거나 같은 자연수이다.

후위 표기식을 앞에서부터 계산했을 때, 식의 결과와 중간 결과가 -20억보다 크거나 같고, 20억보다 작거나 같은 입력만 주어진다.

출력

계산 결과를 소숫점 둘째 자리까지 출력한다.

풀이 과정

1. 피연산자 각각을 딕셔너리 형태로 만들어서 입력받은 값을 대입시킨다.

   • {'A' : 1, 'B' : 2, ... }

2. 일반적인 후위표현식을 푸는 방식

   • 피연산자가 나타나면, 스택에 집어넣는다.
   • 연산자를 만나게 되면, 스택에서 두개의 피연산자를 pop한 후, 연산을 수행한 다음 결괏값을 다시 스택에 집어넣는다.

import sys
from collections import deque

input = sys.stdin.readline
N = int(input().rstrip())
v = list(input().rstrip())

queue = deque()
val_dict = dict()

for i in range(N):
    val_dict[chr(ord('A')+i)] = int(input().rstrip())

for char in v:
    if char in ['*', '+', '/', '-']:
        p1 = queue.pop()
        p2 = queue.pop()
        result = eval(str(p2) + char + str(p1))
        queue.append(result)
    else:
        queue.append(val_dict[char])

print("%.2f"%(queue.popleft()))

문제 설명

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

풀이 과정

1. Union-find 알고리즘 활용하여 각각의 정점이 속하는 집합을 구해준다.
   • Parent 배열에 각각의 정점의 부모노드 저장
2. 집합의 개수를 출력해주면 된다.

소스 코드

import sys

N, M = map(int, sys.stdin.readline().rstrip().split())

parent = [i for i in range(N+1)]
def union(a, b):
    p1 = find(a)
    p2 = find(b)
    if p1 != p2:
        parent[p1] = p2

def find(a):
    if parent[a] != a:
        parent[a] = find(parent[a])

    return parent[a]

for _ in range(M):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    if find(a) != find(b):
        union(a, b)

for i in range(1, N+1):
    find(i)

s = set(filter(lambda x:x>0, parent))
print(len(s))    

문제 설명

문제

석환이는 아기다. 아기 석환이는 자연수가 쓰여져있는 카드를 갖고 다양한 놀이를 하며 노는 것을 좋아한다. 오늘 아기 석환이는 무슨 놀이를 하고 있을까? 바로 카드 합체 놀이이다!

아기 석환이는 자연수가 쓰여진 카드를 n장 갖고 있다. 처음에 i번 카드엔 ai가 쓰여있다. 카드 합체 놀이는 이 카드들을 합체하며 노는 놀이이다. 카드 합체는 다음과 같은 과정으로 이루어진다.

1. x번 카드와 y번 카드를 골라 그 두 장에 쓰여진 수를 더한 값을 계산한다. (x ≠ y)
2. 계산한 값을 x번 카드와 y번 카드 두 장 모두에 덮어 쓴다.

이 카드 합체를 총 m번 하면 놀이가 끝난다. m번의 합체를 모두 끝낸 뒤, n장의 카드에 쓰여있는 수를 모두 더한 값이 이 놀이의 점수가 된다. 이 점수를 가장 작게 만드는 것이 놀이의 목표이다.

아기 석환이는 수학을 좋아하긴 하지만, 아직 아기이기 때문에 점수를 얼마나 작게 만들 수 있는지를 알 수는 없었다(어른 석환이는 당연히 쉽게 알 수 있다). 그래서 문제 해결 능력이 뛰어난 여러분에게 도움을 요청했다. 만들 수 있는 가장 작은 점수를 계산하는 프로그램을 만들어보자.

입력

첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다.

두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, a2, …, an이 공백으로 구분되어 주어진다. (1 ≤ ai≤ 1,000,000)

출력

첫 번째 줄에 만들 수 있는 가장 작은 점수를 출력한다.

풀이 과정

1. 매 순간 가장 작은 카드 두개를 뽑아서 더한 값을 가진 카드 두장을 다시 넣어주어야 한다.
   • 이 때, 가장 작은 카드 두개를 뽑아야 하므로 최소 히프를 사용하였다.
2. 즉, 최소 히프에서 두개를 뽑아서 더한다음, 더한 값을 두번 넣어주면 된다.

소스 코드

import sys
import heapq

n, m = map(int, sys.stdin.readline().rstrip().split())
cards = list(map(int, sys.stdin.readline().rstrip().split()))
heap = []

for card in cards:
    heapq.heappush(heap, card)

for _ in range(m):
    a = heapq.heappop(heap)
    b = heapq.heappop(heap)
    heapq.heappush(heap, a+b)
    heapq.heappush(heap, a+b)

print(sum(heap))

문제 설명

문제

젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다!

젤다의 전설 시리즈의 주인공, 링크는 지금 도둑루피만 가득한 N x N 크기의 동굴의 제일 왼쪽 위에 있다. [0][0]번 칸이기도 하다. 왜 이런 곳에 들어왔냐고 묻는다면 밖에서 사람들이 자꾸 "젤다의 전설에 나오는 녹색 애가 젤다지?"라고 물어봤기 때문이다. 링크가 녹색 옷을 입은 주인공이고 젤다는 그냥 잡혀있는 공주인데, 게임 타이틀에 젤다가 나와있다고 자꾸 사람들이 이렇게 착각하니까 정신병에 걸릴 위기에 놓인 것이다.

하여튼 젤다...아니 링크는 이 동굴의 반대편 출구, 제일 오른쪽 아래 칸인 [N-1][N-1]까지 이동해야 한다. 동굴의 각 칸마다 도둑루피가 있는데, 이 칸을 지나면 해당 도둑루피의 크기만큼 소지금을 잃게 된다. 링크는 잃는 금액을 최소로 하여 동굴 건너편까지 이동해야 하며, 한 번에 상하좌우 인접한 곳으로 1칸씩 이동할 수 있다.

링크가 잃을 수밖에 없는 최소 금액은 얼마일까?

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 동굴의 크기를 나타내는 정수 N이 주어진다. (2 ≤ N ≤ 125) N = 0인 입력이 주어지면 전체 입력이 종료된다.

이어서 N개의 줄에 걸쳐 동굴의 각 칸에 있는 도둑루피의 크기가 공백으로 구분되어 차례대로 주어진다. 도둑루피의 크기가 k면 이 칸을 지나면 k루피를 잃는다는 뜻이다. 여기서 주어지는 모든 정수는 0 이상 9 이하인 한 자리 수다.

출력

각 테스트 케이스마다 한 줄에 걸쳐 정답을 형식에 맞춰서 출력한다. 형식은 예제 출력을 참고하시오.

풀이 과정

1. 기존 다익스트라 알고리즘과는 다르게 distance를 2차원 배열로 해서 구현했던게 특이
   • 현재 좌표 기준으로 상,하,좌,우 이동하면서 거리 갱신 및 최소 히프에 이동하는 좌표 저장
   • 시작점은 [0, 0]이고, 매 순간 배열 범위를 벗어나는지 확인하는 과정 필요
2. 다익스트라 알고리즘이 종료되는 순간, distance[n-1][n-1]을 출력해주면 된다.
   • print('%d'%(변수)) 문법 사용

소스 코드

import sys
import heapq

problem_count = 1
input = sys.stdin.readline
while True:
    n = int(input().rstrip())
    if n == 0:
        break
    matrix = [list(map(int, input().rstrip().split())) for _ in range(n)]
    INT_MAX = int(10e9)
    distance =[[INT_MAX] * n for _ in range(n)]
    heap = []
    distance[0][0] = matrix[0][0]
    heapq.heappush(heap, [matrix[0][0], [0, 0]])
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]
    while heap:
        dist, pos = heapq.heappop(heap)
        if distance[pos[0]][pos[1]] < dist:
            continue
        for i in range(4):
            nx = pos[0] + dx[i]
            ny = pos[1] + dy[i]
            if 0 <= nx and nx < n and 0 <= ny and ny < n:
                if distance[nx][ny] > dist + matrix[nx][ny]:
                    distance[nx][ny] = dist + matrix[nx][ny]
                    heapq.heappush(heap, [dist + matrix[nx][ny], [nx, ny]])
    print("Problem %d: %d"%(problem_count, distance[n-1][n-1]))
    problem_count += 1

문제 설명

문제

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다.

입력

첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.

그리고 M+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다. 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.

풀이 과정

1. 각각의 연결 정보를 토대로 그래프 구성
2. Dijkstra 알고리즘을 활용한다.
   • 거리가 최소인 정점을 뽑아서 연결된 정점들의 거리를 갱신하는 방식
   • 최소 히프를 사용해서 매 순간 거리가 최소인 정점을 빠르게 뽑도록 한다.
3. 저장된 Distance[B]를 출력해주면 된다.

소스 코드

import sys
import heapq

input = sys.stdin.readline

N = int(input().rstrip())
M = int(input().rstrip())
graph = [[] for _ in range(N+1)]

for _ in range(M):
    fr, to, cost = map(int, input().rstrip().split())
    graph[fr].append([cost, to])

A, B = map(int, input().rstrip().split())

INT_MAX = int(10e9)
heap = [[0, A]]
distance = [INT_MAX] * (N+1)
distance[A] = 0

while heap:
    cost, target = heapq.heappop(heap)
    if distance[target] < cost:
        continue
    for n_cost, n_node in graph[target]:
        if distance[n_node] > cost + n_cost:
            distance[n_node] = cost + n_cost
            heapq.heappush(heap, [cost + n_cost, n_node])

print(distance[B])

문제 설명

문제

캡틴 이다솜은 자신의 해적선에 적을 공격하기 위한 대포알을 많이 보관해 놓는다. 다솜이는 미적감각이 뛰어나기 때문에, 대포알은 반드시 사면체 모양으로 쌓아놓아야 한다고 생각한다. 사면체를 만드는 방법은 길이가 N인 정삼각형 모양을 만든다. 그 위에 길이가 N-1인 정삼각형 모양을 얹고 그위에 계속 해서 얹어서 1크기의 정삼각형 모양을 얹으면 된다.

각각의 삼각형은 1, 3, 6, 10 ,..... 와 같이 대포알을 가지고 있다. 따라서 완벽하게 쌓았을 때, 한 사면체에는 1, 4, 10, 20 ,.... 개를 가지고 있을 것이다.

현재 다솜이의 해적선에 대포알이 N개가 있다. 다솜이는 영식이를 시켜서 사면체를 만들게 하고 싶다. 영식이는 물론 하기 싫지만 어쩔수 없이 다솜이가 시키는대로 사면체를 가능한 최소 개수 만큼 만들려고 한다. N개의 대포알로 만들 수 있는 사면체의 최소 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 입력 N이 들어온다. N은 300,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 영식이가 만들 수 있는 사면체 개수의 최솟값을 출력한다.

풀이 과정

1. 사면체가 될수있는 경우의 수를 테이블에 저장 및 DP테이블에 1로 설정한다. (최솟값이므로)
   • 즉, 경우의 수 테이블에는 [1, 4, 10, 20, ... ]이 저장된다.
   • DP[1] = 1, DP[4] = 1, DP[10] = 1, ... 이 저장된다.
2. 이후 Bottom-up 방식으로 DP테이블을 채워나가면 된다.
   • i개 대포알로 만들수 있는 최소 개수를 구할 때, 저장해 둔 경우의 수 테이블의 값들을 j라고 한다면
   • DP[i] = min(DP[i], DP[i-j[k]]) (i-j[k] > 0) 일때
3. 이후 DP[n]을 출력하면 된다.

소스 코드

import sys


N = int(sys.stdin.readline().rstrip())
curr = 1
step = 1
k = 1
area = 1
INT_MAX = int(10e9)
dp = [INT_MAX] * 300001
four = [1]
dp[1] = True
dp[0] = True
# 사면체 경우의 수 구하는 부분
while True:
    if N == area:
        print(1)
        sys.exit(0)
    if N < area:
        break
    k += 1
    curr += k
    area += curr
    four.append(area)
    if area <= 300000:
        dp[area] = 1

# dp 테이블 채우는 부분
for i in range(1, N+1):
    for j in four:
        if i - j > 0:
            dp[i] = min(dp[i], dp[i-j]+1)

print(dp[N])

문제 설명

문제

양팔 저울과 몇 개의 추가 주어졌을 때, 이를 이용하여 입력으로 주어진 구슬의 무게를 확인할 수 있는지를 결정하려고 한다.

무게가 각각 1g과 4g인 두 개의 추가 있을 경우, 주어진 구슬과 1g 추 하나를 양팔 저울의 양쪽에 각각 올려놓아 수평을 이루면 구슬의 무게는 1g이다. 또 다른 구슬이 4g인지를 확인하려면 1g 추 대신 4g 추를 올려놓으면 된다.

구슬이 3g인 경우 아래 <그림 1>과 같이 구슬과 추를 올려놓으면 양팔 저울이 수평을 이루게 된다. 따라서 각각 1g과 4g인 추가 하나씩 있을 경우 주어진 구슬이 3g인지도 확인해 볼 수 있다.

<그림 1> 구슬이 3g인지 확인하는 방법 (1은 1g인 추,4는 4g인 추, ●은 무게를 확인할 구슬)

<그림 2>와 같은 방법을 사용하면 구슬이 5g인지도 확인할 수 있다. 구슬이 2g이면 주어진 추를 가지고는 확인할 수 없다.

추들의 무게와 확인할 구슬들의 무게가 입력되었을 때, 주어진 추만을 사용하여 구슬의 무게를 확인 할 수 있는지를 결정하는 프로그램을 작성하시오.

<그림 2> 구슬이 5g인지 확인하는 방법

입력

첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무게는 500g이하이며, 입력되는 무게들 사이에는 빈칸이 하나씩 있 다. 세 번째 줄에는 무게를 확인하고자 하는 구슬들의 개수가 주어진다. 확인할 구슬의 개수는 7이하이다. 네 번째 줄에는 확인하고자 하는 구슬들의 무게가 자연수로 주어지며, 입력되는 무게들 사이에는 빈 칸이 하나씩 있다. 확인하고자 하는 구슬의 무게는 40,000보다 작거나 같은 자연수이다.

출력

주어진 각 구슬의 무게에 대하여 확인이 가능하면 Y, 아니면 N 을 차례로 출력한다. 출력은 한 개의 줄로 이루어지며, 각 구슬에 대한 답 사이에는 빈칸을 하나씩 둔다.

풀이 과정

1. 추를 오름차순으로 두면서, 각각의 추를 둘 때 가능한 경우의 수는 3가지이다.
   • 추를 왼쪽에 둘 때
   • 추를 오른쪽에 둘 때
   • 현재 추만 오른쪽에 두고 왼쪽에 추를 모두 두었을 때
2. 따라서, 위의 3가지 경우의 수로 DP를 구성하면 된다.
3. 마지막으로 각각의 구슬에 대해, 확인 가능 여부를 출력해주면 된다.

소스 코드

import sys

input = sys.stdin.readline

weights_count = int(input().rstrip())
weights = list(map(int, input().rstrip().split()))

marbles_count = int(input().rstrip())
marbles = list(map(int, input().rstrip().split()))

dp = [False] * 40001
dp[0] = True

for weight in weights:
    canmake = set()
    for i in range(40001):
        if dp[i] == True:
            if i + weight <= 40001:
                canmake.add(i+weight) # 오른쪽에 놓았을때,
            if i - weight >= 0:
                canmake.add(i-weight) # 왼쪽에 놓았을 때
            if weight - i >= 0:
                canmake.add(weight-i) # 현재 물체만 오른쪽에 두고 나머지는 왼쪽에 두었을 때
    for c in canmake:
        dp[c] = True

for marble in marbles:
    if dp[marble] == True:
        print('Y', end=" ")
    else:
        print('N', end=" ")

문제 설명

문제

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 E(1≤E≤200,000)가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호가 빈 칸을 사이에 두고 주어진다.

출력

K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

풀이 과정

• 문제만으론 정확히 어떤 경우에 이분 그래프인지 몰라서 더 찾아보았다.

• 요약해 보면, 색이 0과 1이 있고, a-b가 연결되어 있을때 a와 b의 색이 다르다 보면 된다.

1. bfs를 활용한다.
   1. 현재 색이 0일때, 인접한 노드의 색을 1로 한다.
   2. 현재 색이 1일때, 인접한 노드의 색을 0으로 한다.
2. bfs 진행 도중에 현재 색과 인접한 노드의 색이 같은 경우에는 이분 그래프가 되지 않는다.
3. 전체 정점에 대해서 이분 그래프인 경우에는 True, 아닌 경우에는 False를 리턴한다.

소스 코드

import sys
from collections import deque

input = sys.stdin.readline

K = int(input().rstrip())

def bfs(graph, visited, start):
    visited[start] = 0 # 시작 색은 0
    queue = deque([[start, 0]])
    while queue:
        e, v = queue.popleft() # 현재 색깔
        value = 1 if v == 0 else 0 # 현재 색깔 전환
        for next_edge in graph[e]:
            if visited[next_edge] == -1:
                queue.append([next_edge, value])
                visited[next_edge] = value
            elif visited[next_edge] == v: # 다음 엣지의 색이 현재 색과 같으면 실패
                return False
    return True # 시작 정점에 대한 bfs 성공


for _ in range(K):
    V, E = map(int, input().rstrip().split())
    graph = [[] for _ in range(V+1)]
    for __ in range(E):
        a, b = map(int, input().rstrip().split())
        graph[a].append(b)
        graph[b].append(a)
    visited = [-1] * (V+1)

    answer = True
    for i in range(1, V+1):
        if visited[i] == -1:
            if not bfs(graph, visited, i):
                answer = False
                break

    if answer:
        print("YES")
    else:
        print("NO")

문제 설명

문제

몇 개의 자연수로 이루어진 두 집합 A와 B가 있다. 집합 A에는 속하면서 집합 B에는 속하지 않는 모든 원소를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 집합 A의 원소의 개수 n(A)와 집합 B의 원소의 개수 n(B)가 빈 칸을 사이에 두고 주어진다. (1 ≤ n(A), n(B) ≤ 500,000)이 주어진다. 둘째 줄에는 집합 A의 원소가, 셋째 줄에는 집합 B의 원소가 빈 칸을 사이에 두고 주어진다. 하나의 집합의 원소는 2,147,483,647 이하의 자연수이며, 하나의 집합에 속하는 모든 원소의 값은 다르다.

출력

첫째 줄에 집합 A에는 속하면서 집합 B에는 속하지 않는 원소의 개수를 출력한다. 다음 줄에는 구체적인 원소를 빈 칸을 사이에 두고 증가하는 순서로 출력한다. 집합 A에는 속하면서 집합 B에는 속하지 않는 원소가 없다면 첫째 줄에 0만을 출력하면 된다.

풀이 과정

• 이진 탐색 문제로도 풀 수 있음. B를 정렬한 후, A의 각 원소를 B에서 이진탐색으로 구현하면 될듯?
• Set의 in연산자를 쓰면 빠르게 해결할 수 있음.

1. A의 원소를 정렬한다. (오름차순으로 출력해야 하므로)
2. B를 Set 자료구조로 바꾼다. (찾을때 리스트보다 훨씬 빠름, 또한 중복되는 원소가 없으므로)
3. A의 각 원소가 B에 존재하는지 확인한다.
   • 있으면 따로 리스트에 저장해 둔다.
4. 리스트의 길이와 리스트의 요소들을 출력해주면 된다
   • python에서 * 쓰면 쉽게 리스트의 요소들 출력 가능(" ".join한것과 같음)

소스 코드

import sys


nA, nB = map(int,sys.stdin.readline().rstrip().split())
A = list(map(int, sys.stdin.readline().rstrip().split()))
B = list(map(int, sys.stdin.readline().rstrip().split()))

A.sort()
B = set(B)
answer = []

for a in A:
    if a not in B:
        answer.append(a)

print(len(answer))
if answer:
    print(*answer)

문제

문제

수식은 일반적으로 3가지 표기법으로 표현할 수 있다. 연산자가 피연산자 가운데 위치하는 중위 표기법(일반적으로 우리가 쓰는 방법이다), 연산자가 피연산자 앞에 위치하는 전위 표기법(prefix notation), 연산자가 피연산자 뒤에 위치하는 후위 표기법(postfix notation)이 그것이다. 예를 들어 중위 표기법으로 표현된 a+b는 전위 표기법으로는 +ab이고, 후위 표기법으로는 ab+가 된다.

이 문제에서 우리가 다룰 표기법은 후위 표기법이다. 후위 표기법은 위에서 말한 법과 같이 연산자가 피연산자 뒤에 위치하는 방법이다. 이 방법의 장점은 다음과 같다. 우리가 흔히 쓰는 중위 표기식 같은 경우에는 덧셈과 곱셈의 우선순위에 차이가 있어 왼쪽부터 차례로 계산할 수 없지만 후위 표기식을 사용하면 순서를 적절히 조절하여 순서를 정해줄 수 있다. 또한 같은 방법으로 괄호 등도 필요 없게 된다. 예를 들어 a+b*c를 후위 표기식으로 바꾸면 abc*+가 된다.

중위 표기식을 후위 표기식으로 바꾸는 방법을 간단히 설명하면 이렇다. 우선 주어진 중위 표기식을 연산자의 우선순위에 따라 괄호로 묶어준다. 그런 다음에 괄호 안의 연산자를 괄호의 오른쪽으로 옮겨주면 된다.

예를 들어 a+b*c는 (a+(b*c))의 식과 같게 된다. 그 다음에 안에 있는 괄호의 연산자 *를 괄호 밖으로 꺼내게 되면 (a+bc*)가 된다. 마지막으로 또 +를 괄호의 오른쪽으로 고치면 abc*+가 되게 된다.

다른 예를 들어 그림으로 표현하면 A+B*C-D/E를 완전하게 괄호로 묶고 연산자를 이동시킬 장소를 표시하면 다음과 같이 된다.

이러한 사실을 알고 중위 표기식이 주어졌을 때 후위 표기식으로 고치는 프로그램을 작성하시오

입력

첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식은 주어지지 않는다. 표기식은 알파벳 대문자와 +, -, *, /, (, )로만 이루어져 있으며, 길이는 100을 넘지 않는다.

출력

첫째 줄에 후위 표기식으로 바뀐 식을 출력하시오

풀이과정

1. 식을 순차적으로 한자리씩 방문한다.
2. A, B, C등 피연산자는 그대로 출력해준다.
3. 연산자일 때는 스택에 넣어준다.
   • +, - 연산자일때는 괄호('(')를 만나기 전까지 스택에서 모두 빼주고 넣음(곱하기나 나눗셈보다는 우선순위가 낮고, 덧셈, 뺄셈과는 동등)
   • *, / 연산자 일때는 괄호를 만나기 전까지 스택에서 *과 /를 빼주고 넣는다.(덧셈, 뺄셈보다 우선순위가 높으므로 덧셈,뺄셈 위에 있을 수 있음, 곱하기와 나눗셈은 우선순위가 동등하므로 빼줌)
   • '(' 일때는 그냥 넣어도 되지만, ')'일때는 '('를 만날 때까지 스택에서 연산자들을 빼준다.
   • 맨 마지막에는 스택이 빌때까지 모두 빼준다.
4. 피연산자는 그냥 문자열에 붙여주고, 연산자같은 경우는 pop될때마다 붙여주면 된다.

소스 코드

import sys

t = sys.stdin.readline().rstrip()

op_stack = []
answer = ''
p = ['+', '-', '*', '/', '(', ')']
for s in t:
    if s not in p:
        answer += s
    elif s == '+' or s == '-':
        while op_stack:
            if op_stack[-1] != '(':
                answer += op_stack.pop()
            else:
                break
        op_stack.append(s)
    elif s == '*' or s == '/':
        while op_stack:
            if op_stack[-1] == '*' or op_stack[-1] == '/':
                answer += op_stack.pop()
            else:
                break
        op_stack.append(s)
    elif s == ')':
        while op_stack:
            if op_stack[-1] != '(':
                answer += op_stack.pop()
            else:
                op_stack.pop()
                break
    else:
        op_stack.append(s)

while op_stack:
    answer += op_stack.pop()

print(answer)