[백준] 1541번. 잃어버린 괄호

7094 단어 백준백준

문제

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

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다. 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 식이 주어지는데, 그 조건은 다음과 같다.

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

출력

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

풀이

처음에 접근한 방식

  1. '-' 문자가 처음 나오고, 다시 한번 나오기 직전까지의 부분 문자열 추출하기
  2. 그 부분 문자열을 수식으로 인식하여 덧셈 연산 먼저 수행하기
  3. 전체 식 계산하기

'-' 문자가 나온 지점을 체크하여 부분 문자열을 추출하는 방법이 까다롭고,
추출했다고 해도 그걸 어떻게 수식으로 인식하여 덧셈을 할 것인지 고민...

다른 풀이 참고

https://tooo1.tistory.com/146

'-' 문자가 한번이라도 나오면, (괄호를 풀어서) 그 뒤의 숫자들을 모두 뺄셈으로 계산하자!

  • +, -, \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() 이렇게 작성해도 된다.

좋은 웹페이지 즐겨찾기