잃어버린 괄호

[hsskey]

잃어버린 괄호

문제 해결 과정

Step 1: 문제 이해하기

• 덧셈(+)과 뺼셈(-) 연산자로만 구성된 수식이 있을떄, 괄호를 적절히 넣어 값을 최소화한다 55-50+40 → 55-(50+40)

Step 2: 접근 방법

• 직관적으로 생각하기

  • 해당문제는 특정아이디어에 의해 풀린다 → Greedy! → 최적의 해를 보장하는 문제풀이방법은?

  • [문제해결 아이디어] 뺄셈(-) 연산자를 기준으로 최대한 많은 수를 묶는다

  • 여러개의 마이너스가 존재하는 상황이 있다면?

  • 90+30-20+50-30+60-70+30+20 ➡️ (90+30)-(20+50)-(30+60)-(70+30+20) = - 160

  • 단순화: 덧셈만 있다면??

    • "+"을 기준으로 묶어서 다 더해버림

  • 극대화: 뺄셈이 많다면?

    • "-" 을 기준으로 최대한 많이 묶는다

Step 3: 코드 설계 (수도코드)

1. 입력된 수식을 '-' 기호를 기준으로 분할하여 그룹을 생성한다.
   groups = 수식.split('-')

2. 결과를 저장할 변수 `answer`를 0으로 초기화한다.

3. 각 그룹을 순회하며 처리한다.
   for i = 0 to groups.length - 1:
       - 현재 그룹을 '+' 기호로 분할하고, 각 숫자를 더해 그룹의 합을 구한다.
         curSum = sum(groups[i].split('+'))

       - 첫 번째 그룹은 무조건 더한다.
         if i == 0:
             answer += curSum

       - 첫 번째 그룹이 아닌 경우는 모두 뺀다.
         else:
             answer -= curSum

4. 최종 결과를 출력한다.
   print(answer)

Step 4: 코드 구현

 const fs = require('fs')
 const filePath = process.platform === 'linux' ? '/dev/stdin' : `${__dirname}/input.txt`
 const input = fs.readFileSync(filePath).toString().split('\n')

 let groups = input[0].split('-')
 let answer = 0
 console.log(groups)
 for(let i = 0; i < groups.length; i++) {
    //각 그룹 내부에서 덧셈 연산 적용
    let cur = groups[i].split('+').map(Number).reduce((a, b) => a + b)
    if(i === 0) answer += cur // 첫번쨰 그룹은 항상 덧셈(+)
    else answer -= cur
 }

 console.log(answer)