- 오블완
- 자격증
- C
- programmers
- Algorithm
- Database_Design
- c++
- Univ._Study
- tensorflow
- app
- 리눅스마스터2급
- Baekjoon
- Operating_System
- Python
- Image_classification
- cloud_computing
- codingTest
- Kubernetes
- Unix_System
- Android
- 2023_1st_Semester
- Linux
- Artificial_Intelligence
- Personal_Study
- Java
- kubeflow
- study
- 티스토리챌린지
- SingleProject
- datastructure
코딩 기록 저장소
[백준/Python] 1541번 : 잃어버린 괄호 본문
문제 정보
제목 : 잃어버린 괄호
번호 : 1541번
사용 언어 : Python
문제 링크
https://www.acmicpc.net/problem/1541
1541번: 잃어버린 괄호
첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다
www.acmicpc.net
시간 제한 | 메모리 제한 |
2 초 | 128 MB |
문제
세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.
그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.
괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.
입력
첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.
출력
첫째 줄에 정답을 출력한다.
입출력 예제

나의 풀이
실패한 풀이
-를 기준으로 연산을 진행하면 될 것같아서 -를 높은 우선순위로 두고 후위표기식으로 변환하여 계산했습니다. 하지만 이것은 -가 연속으로 나올 때 값이 다르게 나온다는 문제가 있었습니다. 문제를 너무 어렵게 생각했던 것이 오답의 원인이었던것 같습니다.
math = input()
math_list = []
stack = []
tmp = ""
# +와 -를 우선순위를 나누어 후위표기식으로 변환함
for i in math :
if (i == "+" or i == "-") :
if ( i == "-" ) :
while stack and stack[-1] != "-" :
math_list.append(stack.pop())
stack.append(i)
math_list.append(int(tmp))
tmp = ""
else :
tmp += i
math_list.append( int(tmp))
while(stack) :
math_list.append( stack.pop() )
# 후위표기식에 따른 계산
index = 0
while(len(math_list) != 1) :
if math_list[index] == "+" or math_list[index] == "-" :
if math_list[index] == "+" :
math_list[index] = math_list[index-2] + math_list[index-1]
else :
math_list[index] = math_list[index-2] - math_list[index-1]
math_list.pop(index-2)
math_list.pop(index-2)
index = 0
else :
index += 1
print(math_list[0])
다른 방법
잘 안풀려서 찾아보던중 이 문제를 해결할 간단한 방법을 찾게 되었습니다. 식을 '-'를 기준으로 나누어 math리스트에 저장합니다.
math의 요소만큼 반복하는 for루프를 생성하고, 각 요소를 +를 기준으로 나누어 tmp리스트에 저장합니다. 그리고 tmp리스트의 요소를 정수형으로 변환 후 합을 구해 math_list 리스트에 추가합니다.
for m in math :
sum = 0
tmp = m.split("+") # +를 기준으로 분리하여 각 요소들의 합을 구하여 계산할 리스트에 추가함
for t in tmp :
sum += int(t)
math_list.append(sum)
위의 반복이 끝나면 answer에는 math_list의 처음 요소를 저장합니다. 처음 나오는 수는 무조건 양수이기 때문입니다. 이후 math_list에 순차적으로 접근하며 answer에서 각 요소를 뺍니다. 모든 과정을 거친 후 answer을 출력합니다.
answer = math_list.pop(0)
for m in math_list :
answer -= m
print(answer)
전체 코드
math = input().split("-")
math_list = []
for m in math :
sum = 0
tmp = m.split("+") # +를 기준으로 분리하여 각 요소들의 합을 구하여 계산할 리스트에 추가함
for t in tmp :
sum += int(t)
math_list.append(sum)
answer = math_list.pop(0)
for m in math_list :
answer -= m
print(answer)
'백준 > 그리디 알고리즘' 카테고리의 다른 글
[백준/Python] 1931번 : 회의실 배정 (1) | 2024.01.03 |
---|---|
[백준/Java] 11399번: ATM (1) | 2023.05.25 |
[백준/Java] 11047번: 동전 0 (0) | 2023.05.24 |