블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다.
이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.본 글은 [ 백준 ] 1541번: 잃어버린 괄호를 풀고 작성한 글입니다.
문제
설명
세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.
그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.
괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.
입력
첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.
출력
첫째 줄에 정답을 출력한다.
풀이
접근법
뺄셈 연산자를 만났을 때 다음 뺄셈 연산자를 만나기 전까지 나오는 모든 수들은 합해서 빼야 최소값을 구할 수 있다.
문자열로 값이 주어지기 때문에 현재 이어지는 문자열을 합쳐서 숫자로 만들기 위한 변수와 연산자가 뺄셈을 만났을 때 이전 연산자들의 합을 통해서 정답에 그 값을 누적시키기 위한 임시 배열이 필요하다.
이때 유의할 점은 마지막 숫자가 따로 남기 때문에 이를 처리해주기 위해 입력 문자열 끝에 '+' 연산자를 더해줘야 한다는 것이다.
나의 풀이
접근법을 토대로 문제를 풀면 아래와 같다.
N: str = input() + '+'
answer: int = 0
current_num: str = ""
current_sum: list = []
current_operation: str = '+'
for character in N:
if character == '+':
current_sum.append(int(current_num))
current_num = ""
elif character == '-':
current_sum.append(int(current_num))
if current_operation == '+':
answer += sum(current_sum)
else:
answer -= sum(current_sum)
current_num = ""
current_sum = []
current_operation = '-'
else:
current_num += character
if current_operation == '+':
answer += sum(current_sum)
else:
answer -= sum(current_sum)
print(answer)
Big-O
주어진 문자열의 길이 N만큼 반복문을 수행하면 되기 때문에 시간 복잡도는 O(N)이다.
