1541.잃어버린 괄호

이번에 풀어볼 문제는 잃어버린 괄호이다!

1541번: 잃어버린 괄호

나름대로 규칙성을 찾아서 문제푸는것을 시도했기에 시행착오도 생각보다 적었고 내가 원하는 시간내에 푸는 것에 성공했다.

백준의 분류 중 그리디 알고리즘 Part를 풀고있는데 정답률에 비해 난이도가 어렵게 느껴진다.. 기분탓인가...?

 

---

이 문제는 두 가지 해결점이 필요한다. 첫 번째는 바로 문자열에서 숫자와 괄호를 구별해 내는 로직이 필요하다.

이 점은 그냥 간단한 로직으로 해결했다.  '+' 나 '-' 가 아니면 n이라는 변수를 이용해서 자리값을 측정과 동시에 vector에 숫자를 담는다.

그 뒤 '+' 나 '-' 가 나오면 자릿수 만큼 for문을 이용해서 더하기 누적 연산을 진행해주면된다.

예를 들어 숫자는 123이고 자릿수 n=3이면 자릿수는 3이기 때문에 vector의 값을 하나씩 가져와서 누적 더하기 연산을 한다.

이 때 변수를 하나 더 사용해서 다음 자릿수가 진행될때마다 10씩 곱해주면 간단하게 다음과 같은 결과가 된다.

ex) ( 3 * 1 ) + ( 2 * 1 * 10 ) + ( 1 * 1 * 10 * 10 ) = 123 

---

이런식으로 첫 번째 관문을 통과했다. 

두 번째 관문은 '-'에 달려있다. 간단한 규칙이다 '-'가 나오면 다음에 나오는 '+' 연산까지를 괄호로 묶는 계산을 하면 된다.

예를 들어 50-40+30-20+10 이면 => 50-(40+30)-(20+10) => 50-40-30-20-10 이런식으로 '-' 다음에 나오는 '+' 는 모조리

괄호로 묶어서 계산하면 된다!! 이 규칙만 찾아내면 나머지는 So Easy하다!! 그리고 저번에 풀었던 문제 백준 2529 부등호처럼

마지막에 있는 숫자를 어떻게 계산할 것인지만 판단하면된다 => 이것 역시 똑같다. 그냥 따로 아래에 한번 더 써줄뿐이다.

나는 위의 괄호 로직을 bool 변수를 이용해서 '+'를 '-'로 계산해야하는 상황을 구별해주었다. 또한 계산을 순서대로 생각하면 안된다.

예를 들어 50-30이면 50에서 -30을 해야지가 아니라 50은 일단 저장하고 30 앞에 있는 부호를 보고 연산을 결정해야한다.

50 - 30 + 40 => 50 저장 = >  '-' 파악  => 30 파악 => '+' 파악 ( 이 시점에서 50 - 30 연산 진행 )

부호를 만나면 바로 연산을 하는 것이 아닌 이 다음 연산을 판단하고

그 다음에 나오는 부호를 만나면 이전에 판단한 연산이 진행되는 방식

---

 

< Code 설명 >

#include <iostream>
#include <string>
#include <vector>

using namespace std;


int main() {

	string a; // 문자열을 받아준다.
	cin >> a; // 입력
	int n = 0; // 문자열 내의 숫자의 자릿 수를 파악할 변수
	int k = 1; // 누적연산에 필요한 숫자
	vector<int> v; // 문자열 내의 숫자를 저장할 공간
	int tmp = 0; // 문자열 -> 숫자로 저장될 변수
	int sum = 0; // 문자열의 연산 내용이 저장될 변수
	bool before = true;// 이전 연산을 판단하는 변수

	for (int i = 0; i < a.length(); i++){ //문자열 길이만큼 반복
		if (a[i] == '-'){ // '-'라면
			for (int j = v.size()-1; j >= 0; j--){ //문자열 -> 숫자
				tmp += v[j] * k;
				k *= 10;
			}
			if (before){ // 이전에 '+'로 판단
				sum += tmp; // 이전 연산 '+' 진행
				before = false; // '-'를 만났으므로 괄호로 묶고
                                // 다음 연산은 '-'로 판단
			}
			else{ 이전에 '-'로 판단
				sum += -1 * tmp; // 이전 '-' 연산 진행
			}
			tmp = 0; // 다음 연산을 위해 초기화
			k = 1;   // 다음 연산을 위해 초기화
			n = 0;   // 다음 연산을 위해 초기화
			v.clear(); // 다음 연산을 위해 저장된 숫자 백터 비워줌
		}
		else if (a[i] == '+'){ // '+'가 나오면
			for (int j = v.size() - 1; j >= 0; j--){//문자열 -> 숫자
				tmp += v[j] * k;
				k *= 10;
			} 
			if (before){ // 이전에 '+'로 판단
				sum += 1 * tmp; // 이전 연산 '+' 진행
			}
			else{  // 이전에 '-'로 판단 => -(O+O)괄호로 묶였다는 의미
				sum += -1 * tmp; 
                //지금 만난 '+'는 괄호에 묶였으므로 '-'로 연산 된것임
				before = false; 
                // '+' 다음엔 항상 다른 부호가 나오므로 '-'로 다음연산 판단
			}
			tmp = 0; // 다음 연산을 위해 초기화
			k = 1;   // 다음 연산을 위해 초기화
			n = 0;   // 다음 연산을 위해 초기화
			v.clear(); // 다음 연산을 위해 저장된 숫자 백터 비워줌
		}
		else{
			v.push_back(a[i] - 48); //문자인 숫자를 -> 정수로 저장
			n++; // 숫자의 자릿수 증감
		}
	}
	for (int j = v.size() - 1; j >= 0; j--){ // 마지막 숫자 변환
		tmp += v[j] * k;
		k *= 10;
	}
	if (before) // 이전에 '+'로 판단했다면
		cout << sum + tmp << endl;
	else        // 이전에 '-'로 판단했다면
		cout << sum - tmp << endl;
	return 0;
}

# 부등호 문제에서도 그렇고 이 문제에서도 그렇고 숫자의 자릿수를 체크하는 변수 n과 같은 센스는 자주 사용될 것 같다.

# 문자열에서 숫자만 뽑는 로직도 자주 쓰일 거같으니 기억해두자!!