[백준] 1541번. 잃어버린 괄호
문제
https://www.acmicpc.net/problem/1541
세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다. 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.
입력
첫째 줄에 식이 주어지는데, 그 조건은 다음과 같다.
- 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다.
- 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다.
- 수는 0으로 시작할 수 있다.
- 입력으로 주어지는 식의 길이는 50이하이다.
출력
첫째 줄에 정답을 출력한다.
풀이
처음에 접근한 방식
- '-' 문자가 처음 나오고, 다시 한번 나오기 직전까지의 부분 문자열 추출하기
- 그 부분 문자열을 수식으로 인식하여 덧셈 연산 먼저 수행하기
- 전체 식 계산하기
'-' 문자가 나온 지점을 체크하여 부분 문자열을 추출하는 방법이 까다롭고,
추출했다고 해도 그걸 어떻게 수식으로 인식하여 덧셈을 할 것인지 고민...
다른 풀이 참고
'-' 문자가 한번이라도 나오면, (괄호를 풀어서) 그 뒤의 숫자들을 모두 뺄셈으로 계산하자!
- +, -, \0이 아니면 temp에 저장
- +, -, \0이면 temp 저장한 값을 stoi 함수를 통해 int형 result에 저장
- result에 저장할 때 부호를 minus 플래그 값에 따라 바꿔준다.
#include <iostream>
#include <string>
using namespace std;
int main() {
string s;
cin >> s;
string tmp = ""; // 숫자 하나를 임시 저장하는 변수
int ans = 0;
bool minus = false;
// [] 연산자는 배열 인덱스 범위 넘어도 예외 발생x
for(int i = 0; i <= s.length(); i++){
if(s[i] == '+' || s[i] == '-' || s[i] == '\0'){
if(minus){
ans -= stoi(tmp); // 50 40
}else{
ans += stoi(tmp); // 55
}
tmp = ""; // 임시 변수 초기화
// - 문자가 한번이라도 나오면 그 뒤의 숫자들은 모두 뺄셈 연산
if(s[i] == '-'){
minus = true;
}
}
else{ // tmp 문자열에 숫자 한자리씩 붙이기
tmp += s[i];
}
}
cout << ans << "\n";
return 0;
}
참고
operator [] vs. at()
https://neodreamer-dev.tistory.com/256
at() 연산자는 배열 인덱스 범위를 넘어가면 std::out_of_range 예외를 발생시키지만, [] 연산자는 범위 체크를 하지 않기 때문에 경고만 발생한다.
string의 끝에도 널문자가 있을까?
https://hashcode.co.kr/questions/5777
char형 배열과의 호환성을 위해 string의 끝에도 널문자가 있긴 하다. 다만, string 객체는 size()나 length() 함수로 길이를 알 수 있기 때문에 문자열의 끝을 체크할 때 널문자를 사용하지 않아도 된다. 따라서 앞의 코드에서도 s[i] == '\0'
대신 i == s.length()
이렇게 작성해도 된다.
Author And Source
이 문제에 관하여([백준] 1541번. 잃어버린 괄호), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jxlhe46/백준-1541번.-잃어버린-괄호저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)