괄호문제처럼 스택을 사용한다.

 

여는 괄호 ' ( '가 나오면 스택에 넣고

닫는 괄호 ' ) '가 나오면 두가지 케이스로 구분해 처리한다.

  1. 레이저인 경우
    ()인 경우 레이저인데, 레이저로 잘리는 경우 스택에 넣었던 여는 괄호 하나를 제거해줘야한다.
    그리고 스택에 들어있는 쇠막대기의 수를 확인하여 답에 더해준다. 레이저로 자르는 순간 그만큼 갯수가 추가되기 때문이다.
  2. 쇠막대기의 끝부분인 경우
    ))인 경우 쇠막대기의 끝이다. 왜냐하면 문제에 쇠막대기에는 하나 이상의 레이저가 포함된다고 했기 때문이다.
    그래서 그 경우 스택에서 pop해주고 답에 1을 더해주면 된다.

스택 자료구조를 쓰지 않고, 괄호를 세주는 변수를 사용해도 된다.

#include <string>
#include <vector>
#include <stack>
using namespace std;

int solution(string arrangement) {
    int answer = 0;
    stack<char> s;
        
    for(auto iter = arrangement.begin(); iter != arrangement.end(); ++iter){
        if(*iter == '('){
            s.push(*iter);
        }else{
            s.pop();
            if(*(iter-1) == '('){//laser
                answer += s.size();
            }else{
                answer++;
            }
        }
    }
    
    return answer;
}

괄호로 이루어진 문자열이 들어온다.

스택을 이용해서 괄호를 확인해주면 된다.

 

'('이 나온경우 스택에 넣고 ')'이 나오면 스택에 있던 '('을 빼주면 된다.

스택에 뺄'('가 없는데 ')'이 먼저 들어오는 경우도 잘못된 경우이며,

이제 문자열 확인이 끝났는데 스택에 '('이 남아있는 경우도 잘못된 경우이다.

 

여기서 스택을 직접 사용할 필요는 없고 괄호 카운팅용 정수 변수를 사용해서 구현한다.

 

#include<string>
#include <iostream>
using namespace std;

bool solution(string s)
{
    bool answer = true;
    int cnt = 0;
    
    for(auto el : s){
        if(el == '('){
            cnt++;
        }else{
            cnt--;
        }
        if(cnt<0){
            return false;
        }
    }
    
    if(cnt==0){
        answer=true;
    }else{
        answer=false;
    }

    return answer;
}

카운터를 0으로 초기화하고,

 

'('인 경우 +1

')'인 경우 -1

그리고 카운터가 음수로 변하면 ')'가 먼저 나온게 되므로 false를 반환한다.

 

문자열 전체 순회가 끝나고

카운터가 0이 아니라면 '('이 더 많은 것이므로 false

 

카운터가 0인 경우 true를 반환한다.

 

 

+ Recent posts