Codility Lesson 07 - Brackets( JAVA )

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

Brackets coding task - Learn to Code - Codility

 

문제

- N개의 character들도 이루어진 문자열 S가 주어진다.

- S는 아래와 같으면 올바르게 중첩된 것으로 간주한다.

• 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.

S는 비어있거나, (U), [U], {U} or VW 형태( U, V, W는 올바르게 중첩된 문자열 )

- 예시

"{[()()]}" : 올바른 문자열         -> return 1;

"([)()]" : 올바르지 않은 문자열 -> return 0;

 

제한조건

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

N은 0 ~ 200,000 사이의 정수이다.

S는 "(", "{", "[", "]", "}", ")" 들로만 이루어져 있다.

 

풀이

- 괄호가 열린 만큼 닫혀야지 맞는 문제로 stack 자료구조를 활용하여 풀이

- stack은 LIFO( Last In First Out )

- 괄호들의 짝이 맞아야만 맞을 수 있으므로 S의 개수가 홀수일 경우 예외처리

- S가 비어있을 경우도 예외처리

- '(', '{', '[' 가 들어올 때는 stack에 push

- ')', '}', ']' 차례에서는 stack에서 pop한 값을 확인한다.

 

소스코드

// you can also use imports, for example:
import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(String S) {
        // write your code in Java SE 8
        if( S.length() == 0 ) return 1;
        else if( S.length() % 2 == 1 ) return 0;

        char[] arr = S.toCharArray();

        Stack<Character> stack = new Stack<Character>();
        int answer = 1;
        for( char c:arr ) {
            if( '(' == c || '{' == c || '[' == c ){
                stack.push(c);
            }else{
                if( stack.size() != 0 ){
                    char tmp = stack.pop();
                    if( c == ')' && tmp != '(' ){ 
                        answer = 0;
                        break;
                    }else if( c == ']' && tmp != '['){
                        answer = 0;
                        break;
                    }else if( c == '}' && tmp != '{' ){
                        answer = 0;
                        break;
                    }
                }else {
                    answer = 0;
                }
            }
        }

        return answer;
    }
}

 

 

for문을 돌고 나왔을 때, stack에는 아무것도 없는 상태가 되어야 하는 것을 예외처리에 넣어주지 않음..( 코너 케이스 예외처리 미흡 )

 

최종 소스코드

// you can also use imports, for example:
import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(String S) {
        // write your code in Java SE 8
        if( S.length() == 0 ) return 1;
        else if( S.length() % 2 == 1 ) return 0;

        char[] arr = S.toCharArray();

        Stack<Character> stack = new Stack<Character>();
        int answer = 1;
        for( char c:arr ) {
            if( '(' == c || '{' == c || '[' == c ){
                stack.push(c);
            }else{
                if( stack.size() != 0 ){
                    char tmp = stack.pop();
                    if( c == ')' && tmp != '(' ){ 
                        answer = 0;
                        break;
                    }else if( c == ']' && tmp != '['){
                        answer = 0;
                        break;
                    }else if( c == '}' && tmp != '{' ){
                        answer = 0;
                        break;
                    }
                }else {
                    answer = 0;
                }
            }
        }

        // for문을 다 돌고 전부 짝이 맞았다면 stack은 비어있는 상태여야 함.
        if( stack.size() != 0 ){
            answer = 0;
        }

        return answer;
    }
}