자바스크립트 코딩테스트 강좌, 최솟값을 만드는 괄호 배치 찾기

2023년 10월 10일

문제 설명

주어진 숫자와 연산자들로 이루어진 문자열 s가 주어질 때, 괄호를 적절히 배치하여 만들 수 있는 최솟값을 찾는 문제입니다. s는 숫자와 ‘+’ 및 ‘-‘ 연산자로만 이루어져 있습니다.

예를 들어, 입력으로 "5-3+2"가 주어진다면, 이를 괄호를 적절히 사용하여 최솟값으로 만들 수 있습니다.

따라서 괄호를 어떻게 배치하느냐에 따라 결과값이 달라질 수 있습니다. 아래의 예시를 통해 문제를 보다 명확히 이해해 보겠습니다.

                예시 입력: "5-3+2"
                가능한 결과:
                    1) (5-3)+2 = 4
                    2) 5-(3+2) = 0
                최솟값: 0

입력 형식 및 제약 조건

입력: 문자열 s (1 ≤ s.length ≤ 50) 은 숫자와 ‘+’ 혹은 ‘-‘로 구성되어 있습니다.

출력: 최솟값을 정수로 반환합니다.

문제 풀이 과정

1. 문제 이해 및 분석

문제를 해결하기 위해 가장 먼저 해야 할 일은 괄호가 어떤 형태로 배치될 수 있는지를 명확히 이해하는 것입니다. 위의 예시처럼 각 연산자를 괄호로 감싸서 연산을 그룹화할 수 있습니다. 이러한 그룹화 방식은 최종적으로 산출되는 값에 큰 영향을 미칩니다.

2. Greedy Approach

여기서 최솟값을 찾기 위해 사용할 수 있는 방법 중 하나는 그리디 알고리즘을 사용하는 것입니다. ‘그리디 알고리즘’은 현재 순간에서 가장 최적이라고 판단되는 선택을 하여 문제를 해결해 나가는 방법입니다. 그러나 이 문제에서는 그리디 방식이 항상 최적이라고 할 수는 없으므로 주의가 필요합니다.

3. 입력 문자열 파싱

먼저 입력 문자열을 ‘+’와 ‘-‘ 기호를 기준으로 파싱하여 숫자와 연산자의 배열을 만들어야 합니다. 예를 들어, s = "5-3+2"일 경우, 이를 다음과 같이 분리할 수 있습니다.

                numbers = [5, 3, 2]
                operators = ['-', '+']

4. 최솟값 계산

이제 각 연산자에 대해 접근해야 합니다. ‘-‘가 존재할 경우, 해당 위치에서의 모든 뒷 숫자들은 빼줘야 합니다. 이때 현재 숫자 이외의 숫자들은 모두 더해주어야 합니다. 이 과정을 통해 최솟값을 계산할 수 있습니다.

5. 자바스크립트 구현 코드


function minValue(s) {
    let numbers = s.split(/[-+]/g).map(Number);
    let operators = s.match(/[-+]/g) || [];

    let minValue = numbers[0];

    for (let i = 0; i < operators.length; i++) {
        if (operators[i] === '-') {
            minValue -= numbers[i + 1];
            for (let j = i + 1; j < numbers.length; j++) {
                minValue -= numbers[j];
            }
            break;
        } else {
            minValue += numbers[i + 1];
        }
    }
    return minValue;
}

console.log(minValue("5-3+2")); // 출력: 0

6. 시간 복잡도 분석

위의 알고리즘은 입력 문자열을 한 번 파싱하고, 이후 연산자 및 숫자를 순회하기 때문에 시간 복잡도는 O(n)으로 고려할 수 있습니다. 여기서 n은 입력 문자열의 길이입니다. 이는 충분히 효율적인 접근 방식입니다.

7. 최종 정리

이 문제를 통해 괄호의 적절한 배치가 결과값에 얼마나 큰 영향을 미치는지를 알 수 있었습니다. 또한, 그리디 알고리즘과 배열을 활용하여 문제를 효율적으로 해결하는 방법을 배울 수 있었습니다. 성공적인 코딩테스트를 기원합니다!

© 2023 코드 강좌