[Java/Python] 백준 1541 - 잃어버린 괄호

https://www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

 

혼자 힘으로 풀었는가?: O

알고리즘 분류
 - 수학
 - 문자열
 - 그리디 알고리즘
 - 파싱

문제

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.

그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

출력

첫째 줄에 정답을 출력한다.

 

---

 

처음에는 역시나 고민의 시간을 갖는다.

 

어떻게 풀어야하나... 고민을 하다가 금방 답을 찾았다.

 

+는 한번에 더하고 -를 마지막에 뺀다. 그러면 반드시 최솟값을 구할 수 있다는 것.

 

 

s = input()
num = []
oper = []
input_num = ""
for i in range(len(s)):
  if ord(s[i]) >= ord('0') and ord(s[i]) <= ord('9'):
    input_num += s[i]
  else:
    num.append(int(input_num))
    input_num = ""
    oper.append(s[i])
num.append(int(input_num))

#print(num)
#print(oper)

for i in range(len(oper)):
  if oper[i] == '+':
    #print(type(num[i]))
    if type(num[i]) is int:
      num[i] = num[i]+num[i+1]
      num[i+1] = [num[i], i]
      oper[i] = 'x'
    else:
      num[num[i][1]] = num[i][0] + num[i+1]
      num[i+1] = [num[num[i][1]], num[i][1]]
      oper[i] = 'x'
sum = 0
check = False
for i in range(len(num)):
  if type(num[i]) is int:
    if check == False:
      sum = num[i]
      check = True
    else:
      sum -= num[i]

print(sum)

처음에는 숫자와 기호의 배열을 별도로 만들어 관리를 한 다음

 

숫자 정보가 담긴 배열에 값을 더한 위치를 추가하면서 마지막에 값을 확인한 후 빼는 방식으로 만들었다.

 

예를 들어 

 

55 + 50 - 40 + 30 + 30

 

값이 있다면

 

숫자 리스트는

[55, 50, 40, 30, 30] 이 되며

 

위의 코드대로 동작하고 나면

 

[105, [105, 0], 100, [70, 2], [100, 2] ]

 

위와 같은 형태의 리스트가 만들어지게 된다.

 

이후 다시 반복문을 돌면서 num[i]의 타입이 int형이면 값을 읽고 아니면 통과하는 방식으로 풀이를 했다.

 

---

이후 자바로 똑같이 문제를 풀기 전에

 

문뜩 생각이 들었다.

 

어차피 '+'로 다 더하고 '-'로 마지막에 빼는 거라면
처음부터 '-'로 기준을 나누고 '+'를 따로 다 더해주면 되는 것 아닌가?

그래서 이를 자바로 구현했다.

 

(Java 코드)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException   {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String s = br.readLine();
		String [] arr = s.split("-");
		int total = 0;
		for(int i=0; i<arr.length; i++) {
			int sum = 0;
			if(arr[i].indexOf("+") > -1) {
				String [] arr_sum = arr[i].split("\\+");
				for(int j=0; j<arr_sum.length; j++) {
					sum += Integer.parseInt(arr_sum[j]);
				}
			} else {
				sum = Integer.parseInt(arr[i]);
			}

			if(i == 0) {
				total = sum;
			} else {
				total -= sum;
			}
		}
		System.out.println(total);
	}
}

구조는 단순하다

 

우선 '-'로 나누고

 

나눠진 값을 '+'로 나눠서 다시 더하여 값을 초기화해준다.

 

55+50-40+30-30 일 경우

 

[55+50, 40+30, 30]

 

[105, 70, 30]

 

105-70-30 = 5

의 결과 값을 얻을 수 있게 된다.

 

(Python 코드)

s = input()
arr = s.split("-")
total = 0
for i in range(len(arr)):
  sum = 0;
  if "+" in arr[i]:
    arr_sum = list(map(int, arr[i].split("+")))
    for j in arr_sum:
      sum += j
  else:
    sum = int(arr[i])
  if i==0:
    total = sum
  else:
    total -= sum
print(total)

 

---

Git 백준 1541번 - 잃어버린 괄호.py

Git 백준 1541번 - 잃어버린 괄호.java