Lv2_[올바른 괄호, C++] 풀이 및 알고리즘 정리 - 프로그래머스

 

프로그래머스

문제 내용, 조건, 예시는 프로그래머스 사이트 참조

---

알고리즘

괄호방향에 따라 아래와 같의 정의해서

• '('  =  +1
• ')'  =  -1

덧셋뺄셈으로 문제를 해결할 수 있다.

정의된 값을 가지고 두가지 조건을 만족한다면 알고리즘은 완성

• 조건1) 순차적으로 비교를 하는 중간에는 결과 값이 '0' 아니면 '항상 양수'가 되어야 함
  • -(음수)가 되면 즉시 false
• 조건2) 전부 비교한 후, 결과 값이 0이면 true
  • 0이 아닌 모든 수는 false

- 음수가 되는 경우는 ')'가 '('보다 먼저 들어온 경우
- 결과 값이 0이 아닌 경우는 괄호 짝이 맞지 않는 경우

위의 알고리즘을 코드로 표현을 하면

#include <string>
 
using namespace std;
 
bool solution(string s) {
    bool answer = false;
    int store = 0;
 
    // '(' : +1, ')' : -1
    for(auto c : s) {
        store += (('(' == c) ? 1 : -1);
        if(store < 0) {
            break;
        }
    }
 
    if(store == 0) {
        answer = true;
    }
 
    return answer;
}

 

 

↓↓↓↓↓↓ 유익했다면 하트 뿅 ♥ ↓↓↓↓↓↓