백준 1541 - 잃어버린 괄호

문제

알고리즘 분류)

• 수학
• 문자열
• 그리디
• 파싱

풀이

'+' 와 '-' 연산으로 되어있는 수식을 괄호를 배치하여 가장 적은 값을 만드는 문제이다

핵심 : '-'이후에 나오는 숫자들은 그 다음 '-'가 나오기 전까지 모두 묶어준다

왜냐하면 빼주어야 할 값을 최대로 만들어 주어야 하기 때문
예) 10+20+30-40+50+60-10 일때
==> 10+20+30-(40+50+60)-(10)
과 같이 괄호를 생성해주면 값이 최소이다

그 이후는 적절한 split과 문자열의 다룸으로 구현이 필요한 듯 하다

소스코드

python)

text = input().split('-')
array=[]
add_array=[]
sub_array=[]

for i in range(len(text)):
    if i == 0:
        a = text[i].split('+')
        for j in a:
            add_array.append(int(j))
    
    else:
        a = text[i].split('+')
        for j in a:
            sub_array.append(int(j))

        
    
print(sum(add_array)-sum(sub_array))

더해줄 값을 모은 배열 : add_array
빼줄 값을 모은 배열 : sub_array
를 만들고

입력값은 양수부터 주어지므로 text[0]의 숫자들은 모두 더해져야할 값이다
그 이후에는 모조리 빼주어야 할 숫자들이 들어있는 것이다

반복문을 이용하여 '+'를 제외해주고 정수로 변환하여 알맞은 배열에 넣어주었다

java script)

let input = require("fs").readFileSync("/dev/stdin").toString();

const numbers = input.split(/\-|\+/gi).map((v) => parseInt(v));
const symbols = input.match(/\-|\+/gi);
let array = [];

for (let i = 0; i < numbers.length; i++) {
  array.push(numbers[i]);
  if (i !== numbers.length - 1) array.push(symbols[i]);
}

let result = array[0];
let mode = array[1];
for (let i = 2; i < array.length; i++) {
  const currValue = array[i];
  if (typeof currValue === "number")
    mode === "+" ? (result += array[i]) : (result -= array[i]);
  else if (currValue === "+") continue;
  else mode = "-";
}
console.log(result);

입력받은 텍스트를 배열에 [50, '-', 30, '+', 20]과 같은 형태로 만들고
for문으로 순회하며 mode값에 따른 연산처리를 해주었다