[P&B] #3 Programmers

프로그래머스 Lv.2 스택/큐

 

올바른 괄호

문제 설명

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어

• "()()" 또는 "((())()"는 올바른 괄호입니다.
• ")()(" 또는 "(()("는 올바르지 않은 괄호입니다.

'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

 

제한 조건

문자열 s의 길이 : 100,000 이하의 자연수

문자열 s는 '(' 또는 ')'로만 이루어져 있습니다.

 

문제 풀이 코드

import java.util.Stack;
class Solution {
    static boolean solution(String s) {
        boolean answer = true;

        Stack<String> str = new Stack<>();
        for (String string : s.split("")) {
            if (string.equals("(")) {
                str.push("y");
            }
            else {
                if(str.empty())
                    return false;
                str.pop();
            }
        }
        if (!str.empty())
            answer=false;
        return answer;
    }
}

 

다른 사람의 문제 풀이 코드

import java.util.Stack;
class Solution {
    boolean solution(String s) {
        boolean answer = true;  
        String res = "YES";
        Stack<Integer> st = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '('){
                st.push(1);
            } else if (s.charAt(i) == ')') {
                if (st.isEmpty()) {
                    answer = false;
                    break;
                } else {
                    st.pop();
                }
            }
        }

        if(!st.isEmpty()) {
            answer = false;
        }

        System.out.println(res);
		return answer;
    }   
}

 

문제 풀이 코멘트

stack을 사용하지 않고도 풀 수 있는 방법이 있다는 걸 알고있었지만 자료구조를 공부하기 위해 문제를 푼것이기 때문에 출제자의 의도에 맞게 스택을 사용하려고 했다. 정확도 면에서는 100%였지만 효율성 부분에서는 두가지 테스트케이스 모두 시간 초과가 떴고 결국 이를 해결하지 못했다. 다른 사람의 코드와의 차이점을 보면 향상된 for문 사용여부와 스택의 자료형 차이였다. 그래서 내 코드에서 향상된 for문을 일반 for문으로 바꾸고 s를 split하여 string.equals("(")으로 구현한 것을 s.charAt(i) == '('로 바꾸었다.그랬더니 효율성 테스트도 통과했다. split을 하여 .equals를 호출하는 과정이 charAt하나로 구현되면서 효율성이 증가한것으로 예상된다. 다음부터 효율성이 떨어진다면 같은 의미의 다른 코드방법으로 구현을 해봐야겠다.