[1541번] 잃어버린 괄호

문자열, 그리디, 211114

문제

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

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

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

입력

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

출력

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

예제 입력 1

Plain Text
복사

예제 출력 1

Plain Text
복사

예제 입력 2

10+20+30+40
Plain Text
복사

예제 출력 2

Plain Text
복사

예제 입력 3

Plain Text
복사

예제 출력 3

Plain Text
복사

My solution

function solution(i) {
    const input = i.toString().trim();
	   const regExp = /(\d{1,5})|([+-])/g; // 숫자만 1~5개 나오거나, +,-이

    const splitArr = input.match(regExp);

    // console.log(input, input.match(regExp));
    const sum = 0;
    for (let i = 1; i < splitArr.length; i += 2) {}
}

test('solution', () => {
    expect(solution(`55-50+40`)).toStrictEqual('-35');
    // expect(solution(`10+20+30+40`)).toStrictEqual('100');
    // expect(solution(`00009-00009`)).toStrictEqual('0');
});
JavaScript
복사

위와 같이 하면 너무 연산이 복잡해진다. 더 빨리 하는 방법이 있다. 역시 수학적인 감이 있어야 한다. 부호는 그냥 숫자 앞에 붙여서 한꺼번에 계산이 가능한 것이었다.

그래서 처음 마이너스 - 기호를 만나면 뒤의 모든 숫자들을 한번에 빼주려고 했다. 왜냐하면 한번에 빼지 않으면 최대로 빼줄 수 없다.

그 예시가 55 - 50 + 40이다. -50을 만나자마자 -50을 해줬다면 35가 답이 되지만 마이너스 뒤로 전부 더했다가 한번에 빼줘서 -35가 되었다.

다시 말해, 마이너스 기호를 기준으로 한번 자르고 그뒤로 한번에 빼버린다.

const input = i.toString().trim();
const splitArr = input.split('-');
JavaScript
복사

그리고 마이너스 앞에 있는 숫자는 크게 상관이 없다. 뒤에서 크게 빼주는 것이 중요하다.

그래서 preOperand로 두고 앞의 값들의 합을 구해주었다. 그다음 앞의 값들은 날려버렸다.

let preOperand = +splitArr[0]
        .split('+')
        .map(v => +v)
	      .reduce((c, a) => c + a);
let sum = 0;
splitArr.shift();
JavaScript
복사

그다음 preOperand는 날라간 상태이므로 그 뒤는 마이너스되어질 숫자이므로 +를 만날 때마다 postOperand에 담아서 모두 더해놓는다. 한번에 빼기 위해서.

+는 여러개가 나타날 수 있을 것이다. 그래서 for문을 통해 splitArr를 돌면서 나눠서 합을 계속 누적해놓는다.

for문이 다 돌고나면 누적된 sum을 preOperand에 빼면 최대로 빼줄 수 있다.

for (const y of splitArr) {
    const postOperand = y.split('+').map(v => +v);
    for (const x of postOperand) {
        sum += x;
    }
    // console.log(y, postOperand, sum);
}
preOperand -= sum;
JavaScript
복사

백준 문제를 풀면서 자주 느끼는 것이지만 수학적인 감이 더 중요한 것 같다. 아니면 에지케이스처리가 너무 복잡해지고 너무 불필요한 연산이 많아진다. 이렇게 불필요한 연산들을 줄이고 깔끔한 알고리즘을 짜기 위해서는 수학문제를 디테일하게 하나하나 체크해가면서 식을 만들어가는 과정이 필요하다. 직관적으로만 해결하기는 힘든 문제들이다. 내 생각에는 이런 문제들에 대해서 익숙해지는 것이 더 빠를 것 같다. 문제들에 대한 경험이 너무 부족해서 창의력을 발휘하지 못하는 것 같다.

나는 처음에 위 문제에서도 굳이 부호와 숫자를 모두 나눠서 splitArr를 만들기 위해서 정규표현식을 가져와서 사용했고 잘 나누기는 했지만 나눌 이유가 없는데 쓸 데 없는 작업을 한 것이다.

정답을 구하기 위해서 어떻게 연산을 해야 하는지에 대해 여러 가지 케이스들을 가지고 와서 분석해야 하는 것이다. 일단은 노트에 여러 개의 테스트 케이스를 가져와서 분석해야 한다.

만약 그래도 전혀 감이 안온다면 다른 사람의 설명을 보면서 반드시 익혀야 된다. 이것은 비슷한 수학 문제가 분명히 있었을 텐데 내가 잊어버렸거나 많이 풀어보지 않아서 생긴 문제라고 생각했다.

소스코드

function solution(i) {
    const input = i.toString().trim();
    const splitArr = input.split('-');
    // console.log(splitArr);
    let preOperand = +splitArr[0]
        .split('+')
        .map(v => +v)
        .reduce((c, a) => c + a);
    let sum = 0;
    splitArr.shift();

    for (const y of splitArr) {
        const postOperand = y.split('+').map(v => +v);
        for (const x of postOperand) {
            sum += x;
        }
        // console.log(y, postOperand, sum);
    }
    preOperand -= sum;
    console.log(preOperand);

    return preOperand.toString();
}

test('solution', () => {
    expect(solution(`55-50+40`)).toStrictEqual('-35');
    expect(solution(`10+20+30+40`)).toStrictEqual('100');
    expect(solution(`00009-00009`)).toStrictEqual('0');
});
JavaScript
복사