ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 1541.잃어버린 괄호
    알고리즘/백준 BAEK JOON 2020. 5. 18. 23:48

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

     

    1541번: 잃어버린 괄호

    첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다

    www.acmicpc.net

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

    백준의 분류 중 그리디 알고리즘 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과 같은 센스는 자주 사용될 것 같다.

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

    '알고리즘 > 백준 BAEK JOON' 카테고리의 다른 글

    2667.단지번호붙이기  (0) 2020.05.21
    15649 ~ 15652.N과 M(1~4)  (0) 2020.05.20
    1541.잃어버린 괄호  (2) 2020.05.18
    2529.부등호  (0) 2020.05.18
    1138.한 줄로 서기  (0) 2020.05.17
    1120.문자열  (0) 2020.05.17

    댓글 2

Designed by Tistory.