본문으로 바로가기

Description

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:

class Solution { public 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 ")".

Solution 1. Stack

public int solution(String S) {
      if(S.length() % 2 != 0){return 0;}
      Stack<Character> stack = new Stack<>();
      for(char c : S.toCharArray()){
          switch(c){
              case '(' : stack.push(')'); break;
              case '[' : stack.push(']'); break;
              case '{' : stack.push('}'); break;
              default :
                  if(stack.isEmpty() || stack.pop() != c){
                      return 0;
                  }
                  break;
          }
      }
      return stack.isEmpty()? 1 : 0;
}

스택을 이용하여 열린 괄호문자가 왔을경우 다음에 와야하는 괄호 문자열을 지정하여 넣어줍니다. 닫힌 괄호가 들어왔을때 stack에 마지막에 들어온 닫힌 괄호문자열과 비교하여 불일치 할경우 0을 반환해줍니다. 끝까지 진행하여 스택에 아무 데이터가 없으면 1을 반환하고 그외 케이스는 0입니다.

Reference

 

Brackets coding task - Learn to Code - Codility

Determine whether a given string of parentheses (multiple types) is properly nested.

app.codility.com

코딜리티, Codility, 알고리즘, 코딩테스트, 코테, 문제풀이, Algorithm, String, Hash Table, LinkedList, Depth-First Search, Breadth-First Search, Matrix, TwoPoint, Array, Recusion,

Binary Tree, Recusion, 전위순회, inorder-traversal