[알고리즘] 백준 1541 잃어버린 번호 (javascript)

문제

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

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

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

 

입력

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

 

나의 풀이

let fs = require('fs')
let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n')[0]

let filteredArray = input.split('-')

let answer = 0;
for (let i = 0; i< filteredArray.length; i++){
   let number = filteredArray[i].split("+").map(Number).reduce((a,b)=>a+b)
   if(i===0){
       answer+=number
   }else{
       answer-=number
   }
}
console.log(answer)

 

이 문제는 처음 아이디어만 떠올리면 굉장히 쉬운 문제이다.

괄호의 위치로만 작은 수를 만들어 내야 하기 때문에 음수가 클수록 유리하다.

따라서 마이너스 부호를 기점으로 모든 수를 괄호로 묶어내면 가장 작은 수가 만들어진다.

 

만약 입력이 "55-50+40" 이라고 가정하자.

먼저 마이너스 부호를 기점으로 모든 수를 정렬해야 하므로 '-' 로 split을 한다.

그렇다면 ["55", "50+40"] 배열이 생성될 것이다. (이것을 filteredArray라고 하자)

이제 각 원소에 문자형 숫자, 혹은 +가 섞인 문자형 숫자가 존재하게 된다.

 

이제는 filteredArray의 각 원소의 계산을 하기 위해 for문을 사용한다.

"+"를 계산하기 위해 각 원소를 +로 split한 뒤, 그 값을 map을 통해 Number로 변환해 주고, reduce를 이용해 모두 합한다.

(첫 번째 원소인 "55"는 +가 없으므로 [55]가 되고, 이 배열의 합은 55이다.)

(두 번째 원소인 "50+40"은 [50,40]이 되고, 이 배열의 합은 90이다.)

 

여기서 중요 포인트는, 첫 번째 원소는 더해줘야 한다는 것이다.

filteredArray에서 첫 번째 원소만 양수이고 나머지 수는 앞의 부호가 ("-")이므로 음수이다.

(첫 번째 원소는 55이므로 answer 에 55를 더해준다.)

(두 번째이자 마지막 원소인 90은 answer에서 빼준다.)

그럼 정답은 -35 이다.

 

따라서 나는 if문을 통해 배열의 0번 인덱스는 answer에 더해주고, 나머지는 answer에서 빼줬다.