백준 1541 잃어버린 괄호 c++ [컴공과고씨]

https://www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

문제를 보고 -가 있는 순간 뒤에 나오는 모든 숫자를 - 처리해주면 최소값이 된다.

위 아이디어를 생각해내면 풀리는 문제였다. 이유는 -가 있으면 뒤에 숫자는 괄호를 활용하여 +가 나오든 -가 나오든 모든 숫자를 -로 처리가 가능하기 때문이다.

 

단계별 문제 풀이

1. 더해야할 숫자, 빼야할 숫자 저장하는 배열 선언

2. 전에 -가 부호가 나왔는지 저장하는 bool 변수 선언 (초기값 : true)

3. +부호를 만났을 때 앞쪽에 -가 나오지 않았을 경우 숫자를 더해야할 배열에 넣어줌

4. - 부호가 있었을 때는 빼야할 배열에 넣어줌

5. - 부호를 만났을 때 앞쪽에 +밖에 없었을 경우 숫자는 더해야할 배열에 넣어주고

bool 함수를 false로 만들어 -가 있다는 것을 알려줌

6. - 부호를 만났을 때 앞쪽에 -가 있었다면 빼야할 숫자에 더해줌

7. 마지막으로 위 방식은 부호를 만나면 앞쪽 숫자를 연산하는 방식이므로 마지막 숫자도 앞에 -가 있었는지 없는지 확인하고 배열에 숫자를 넣어주어야함

 

전체코드

#include <iostream>
#include <string>
using namespace std;
int main(){
    int p_num = 0; // 더해야할 숫자
    int m_num = 0; // 빼야할 숫자
    string s;
    cin >> s;
    bool before_sign = true; // -부호가 나타났는지 확인 (초기값:+)
    int before_index = 0; // 탐색해야할 시작점 인덱스 저장
    for (int i = 0; i < s.length(); i++){
        if(s[i] == '+'){ // + 부호를 만났을 때
            if(before_sign){// - 부호가 없었을 때
                p_num += stoi(s.substr(before_index, i));
                // 숫자 시작점 부터 부호 앞 문자열까지 자름
                // 숫자만 골라서 정수형 변환 후 더해야할 배열에 넣음
                before_index = i + 1; 
                //다음 숫자 시작 점을 지정
            }else if(!before_sign){ // - 부호가 있었을 때
                m_num += stoi(s.substr(before_index, i));
                //빼야할 배열에 넣음
                before_index = i + 1;
            }
        }else if(s[i] == '-'){ // - 부호를 만났을 때
            if(before_sign){ // -가 나오지 않은 경우
                p_num += stoi(s.substr(before_index, i));
                before_index = i + 1;
                before_sign = false;
                // - 부호가 나왔다는 것을 표시
            }else{
                m_num += stoi(s.substr(before_index, i));
                before_index = i + 1;
            }           
        }
    }
    //위 코드는 부호가 나왔을 때 앞의 수를 더해주는 방식이므로 
    //마지막에 나오는 숫자를 더해주어야함.
    if(before_sign){
        p_num += stoi(s.substr(before_index));
    }else{
        m_num += stoi(s.substr(before_index));
    }  
    cout << p_num - m_num;
    return 0;
} // 23min

체감 난이도	걸린시간	참고	사용 알고리즘, 문법
하	23min	x	수학, string

 

yea!