[codility] Brackets

Brackets

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

Task Score

100%

Correctness

100%

Performance

100%

---

 

오랜만에 풀어보는 코딜리티문제~!

요새 스택 문제가 풀어보고싶었는데 딱 좋은 문제를 만났다.

 

// 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) {
        Stack<Integer> st = new Stack<>();
        
        for (char c : S.toCharArray()) {
            switch(c) {
                case '(':
                    st.push(1);
                    break;
                case '{':
                    st.push(2);
                    break;
                case '[':
                    st.push(3);
                    break;
                case ')':
                    if (st.size() <= 0) return 0;
                    if (st.pop() != 1) return 0; 
                    break;
                case '}':
                    if (st.size() <= 0) return 0;
                    if (st.pop() != 2) return 0; 
                    break;
                case ']':
                    if (st.size() <= 0) return 0;
                    if (st.pop() != 3) return 0; 
                    break;
            }
        }
        
        if (st.size() > 0) return 0;
        
        return 1;
    }
}

 

주어진 문자열이 properly nested 되어있는지 체크해서 중첩이 잘되어있으면 1, 아니면 0을 반환한다.

여는 괄호가 나오면 스택에 하나하나 쌓고, (나는 임의로 소괄호 1, 중괄호 2, 대괄호 3으로 값을 부여했다.)

닫는 괄호가 나오면 그에 맞는 여는 괄호가 있는지 스택에서 꺼내서 확인한다.

맞지않는 짝이 나오지 않거나 모든 루프를 돌았는데도 스택에 값들이 남아있다면

해당 문자열은 적절히 중첩이 되어있지 않다는 뜻이므로 0을 반환한다.

 

예를들면,

S="{[()()]}"일 때, 스택에는 이렇게 쌓인다.

---

push(3) -> 3

push(2) -> 32

push(1) -> 321

pop(1) -> 32

push(1) -> 321

pop(1) -> 32

pop(2) -> 3

pop(3) ->

---

짝도 잘 맞고, 마지막에 남아있는 값도 없다.

적절하므로 1을 리턴한다.

 

S="([)()]"일 때는 스택에는 이렇게 쌓인다.

---

push(1) -> 1

push(2) -> 12

pop(1) ==> 에러발생!!!

---

스택 맨 위에 2[가 있는데 1(을 꺼냈기때문에 적절하지 않다.

0을 리턴한다.