[Codility] Lesson4. Brackets

🔮문제

A string S consisting of N characters is considered to be properly nested if any of the following conditions is true:

• S is empty;
• S has the form "(U)" or "[U]" or "{U}" where U is a properly nested string;
• S has the form "VW" where V and W are properly nested strings.

For example, the string "{[()()]}" is properly nested but "([)()]" is not.

Write a function:

int solution(string &S);

that, given a string S consisting of N characters, returns 1 if S is properly nested and 0 otherwise.

For example, given S = "{[()()]}", the function should return 1 and given S = "([)()]", the function should return 0, as explained above.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [0..200,000];
• string S consists only of the following characters: "(", "{", "[", "]", "}" and/or ")".

🔮풀이

stack 자료구조를 사용해서 푸는 전형적인 괄호 문제.

 

 

🔮코드

 #include <algorithm>
 #include <stack>
 #include <iostream>
/*
S가 올바르면 1, 아니면 0을 반환
*/
int solution(string &S) {
  int size = S.size();
  stack<char> st;

  for(int i=0; i<size; i++){
      if(S[i] == '(' || S[i] == '{' || S[i] == '['){
          st.push(S[i]);
      }
      else{
          char ch;
          if(st.empty()){
              return 0;
          }
          ch = st.top();
          if(S[i] == ')'){
              if(ch == '('){
                  st.pop();
                  continue;
              }else{
                  return 0;
              }
          }
          else if(S[i] == '}'){
              if(ch == '{'){
                  st.pop();
                  continue;
              }else{
                  return 0;
              }
          }
          else if(S[i] == ']'){
              if(ch == '['){
                  st.pop();
                  continue;
              }else{
                  return 0;
              }
          }
      }
  }
  if(!st.empty()){
      return 0;
  }
  return 1;
}