C++ 코딩테스트 강좌, 최솟값을 만드는 괄호 배치 찾기

문제 설명

어떤 수식이 주어질 때, 괄호를 적절하게 배치해서 수식의 최솟값을 만드는 방법에 대해 공부해 봅니다. 예를 들어, “1+2-3+4″라는 수식이 있다고 가정할 때, 괄호를 배치하여 가능한 최솟값을 찾는 문제입니다.

문제 정의

주어진 양의 정수와 연산자 (+, -)로 이루어진 문자열이 있을 때, 괄호를 적절히 배치하여 그 수식의 최솟값을 구하는 알고리즘을 작성해보세요. 숫자는 1 이상 100 이하이며, 연산자는 최대 100개까지 있을 수 있습니다.

입력 형식

입력은 하나의 문자열로 주어집니다. (예: “5-3+1-2”)

출력 형식

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

문제 접근 방식

이 문제를 해결하기 위해서는 수식의 사칙연산과 괄호의 우선순위에 대해 이해하고, 각 연산의 결과를 최솟값으로 조정해야 합니다. 괄호를 적절히 사용하여 더하기 연산과 빼기 연산의 계산 순서를 조정할 수 있습니다.

아이디어

수식을 분석할 때, ‘+’ 연산자는 그 앞뒤의 숫자들을 더하는 반면, ‘-‘ 연산자는 그 다음에 오는 모든 숫자를 함께 빼기 때문에 이 점을 잘 활용해야 합니다. 그럼으로써 “-” 연산자 다음의 숫자들을 그룹화하여 더 큰 값을 빼는 방식이 최솟값을 만드는 핵심 전략이 됩니다.

문제 해결 과정

1단계: 수식 파싱하기

입력된 수식을 ‘+’와 ‘-‘를 기준으로 나누어 숫자와 연산자를 분리합니다. 이를 통해 연산 순서를 조절할 수 있는 기초적인 자료구조를 마련합니다.

2단계: 연산자 처리하기

첫 번째 숫자를 초기값으로 설정하고, 이를 시작점으로 하여 ‘+’ 연산자는 해당 숫자와 다음 숫자를 더하고, ‘-‘ 연산자는 그 뒤의 모든 숫자를 빼는 방식으로 계산을 진행합니다.

3단계: 최솟값 계산하기

마지막으로 모든 연산 결과를 바탕으로 최종적으로 만들어진 값에서 최솟값을 도출합니다.

C++ 코드 구현

아래는 위의 접근 방식을 C++로 구현한 예시 코드입니다.

        
#include 
#include 
#include 
#include 

using namespace std;

int minValue(string expression) {
    vector numbers;
    vector operations;
    istringstream iss(expression);
    string temp;

    // 수식 파싱
    while (getline(iss, temp, '+')) {
        size_t pos = 0;
        while ((pos = temp.find('-')) != string::npos) {
            numbers.push_back(stoi(temp.substr(0, pos)));
            operations.push_back('+');
            temp = temp.substr(pos + 1);
        }
        numbers.push_back(stoi(temp));
        operations.push_back('-');
    }

    // 마지막 연산에서 '-' 연산자의 위치를 찾아 최솟값을 계산
    int result = numbers[0];
    bool subtractMode = false;

    for (int i = 1; i < numbers.size(); ++i) {
        if (operations[i - 1] == '-') {
            subtractMode = true;
        }
        if (subtractMode) {
            result -= numbers[i];
        } else {
            result += numbers[i];
        }
    }
    return result;
}

int main() {
    string expression;
    cout << "수식을 입력하세요: ";
    cin >> expression;

    int result = minValue(expression);
    cout << "최솟값: " << result << endl;
    return 0;
}

코드 설명

위의 코드는 입력된 수식을 분석하고 연산을 수행하여 최솟값을 찾아내는 과정입니다. 각 숫자와 연산자를 벡터에 저장한 후, 연산자의 우선순위에 맞게 계산을 진행합니다.

결과 및 테스트

예를 들어, 입력으로 “5-3+1-2″를 제공할 경우, 이 코드는 다음과 같은 과정을 거쳐 최솟값을 구합니다:

5 – 3 + 1 – 2 = 1

결과적으로 1이 출력되며, 이는 파라미터에 따라 결과가 다르게 나올 수 있습니다. 다양한 수식을 통해 테스트가 이루어져야 합니다.

마무리

괄호 배치 문제를 풀기 위해서는 수식의 구조를 이해하고, 각 연산의 효과를 최대한 활용하는 것이 중요합니다. 특히, ‘-‘ 연산자를 활용하여 숫자의 조합에 따른 최솟값을 찾는 방법은 여러 문제에서도 적용될 수 있는 유용한 전략입니다.

C++ 언어의 특성을 잘 활용하여 문제를 풀고, 알고리즘의 복잡성을 줄일 수 있는 optimalsolution을 개발하는 것이 취업 준비에 큰 도움이 됩니다. 이 수업이 여러분의 성공적인 코딩 테스트 준비에 기여하길 바랍니다.