Lesson7 - Brackets

https://app.codility.com/programmers/lessons/7-stacks_and_queues/brackets/

Brackets coding task - Learn to Code - Codility

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 ")".
  
  

package codility.num4;

import java.util.Stack;

public class Brackets {
    public int solution(String S) {
        // write your code in Java SE 8
        char[] arr = S.toCharArray();

        Stack<Character> stack = new Stack<>();

        for(char word : arr){
            if(word == '('){
                stack.push('(');
            }else if(word == '{'){
                stack.push('{');
            }else if(word == '['){
                stack.push('[');
            }else if(word == ')'){
                // 앞에 짝 괄호라든지 아무것도 없는데 닫는 괄호가 나오면 return 0
                if(stack.size() == 0) return 0;
                // 가장 상위에 있는 것을 꺼냈을때 짝이 아니면 return 0
                if(stack.pop() != '(') return 0;
            }else if(word == '}'){
                if(stack.size() == 0) return 0;
                if(stack.pop() != '{') return 0;
            }else if(word == ']'){
                if(stack.size() == 0) return 0;
                if(stack.pop() != '[') return 0;
            }
        }

        if(stack.size() > 0){
            return 0;
        }else{
            return 1;
        }

    }

    public static void main(String[] args) {
        Brackets brackets = new Brackets();
        System.out.println(brackets.solution("[{}]"));
    }
}

- 주어진 문자열이 알맞게 짝지어져있는지 확인하는 문제!

- 일단 스택자료구조 사용하여, S배열을 돌면서여는 괄호일 경우 스택에 push해주고,

- 닫는 괄호를 만났을 경우 스택의 가장 상위 요소를 pop()했을때 짝 괄호가 아니라면 return 0

- 또는 stack의 size가 0이면 return 0

- for문을 다 돌았을때 stack의 size가 0이 아니라면 return 0

- size가 0이라면 return 1