[Programmers Level 2] 올바른 괄호

문제

프로그래머스

 

첫번째 시도

넘어온 괄호 문자열을 split으로 자른 후, 열린 괄호일 경우 스택에 push, 닫는 괄호일 경우 pop해서 스택이 비어있는지 여부를 반환하는 방법으로 시도했다.

import java.util.*;

class Solution {
    boolean solution(String s) {

        String[] temp = s.split("");
        Stack<String> stack = new Stack<>();
        
        // 닫는 괄호로 시작하거나 여는 괄호로 끝나면 false 반환
        if (temp[0].equals(")") || temp[temp.length-1].equals("(")) {
            return false;
        }
        
        for (int i = 0 ; i < temp.length ; i ++) {
            if (temp[i].equals("(")) { // 여는 괄호일 경우 stack에 push
                stack.push(temp[i]);
            } else { // 닫는 괄호일 경우 pop
                
                if (stack.isEmpty()) {
                    return false;
                }
                
                stack.pop();    
                
            }
        }

        return stack.isEmpty();
    }

 

결과

효율성 점수 빵점..

 

---

 

두번째 시도

split 하는 과정을 생략하고 String의 charAt 메서드를 사용해서 괄호를 비교하는 방법을 사용했다. split 메서드 실행 시 문자열을 분리하고, 배열에 삽입하는 과정까지 들어가기 때문에 시간복잡도는 O(n^2)이 되어서 그런 것 같다! 

 

그리고 for문에 들어가기 전 문자열 맨 앞의 괄호가 닫힌 괄호일 경우, 문자열 맨 뒤의 괄호가 열린 괄호일 경우 바로 false를 리턴하는 방법이 효율성을 높여줄 줄 알았는데 아니었다..^^ 비교 해보니까 효율성 테스트 시간에 + 3 ~ 4ms 로 나와서 해당 코드는 제거했다.

import java.util.*;

class Solution {
    boolean solution(String s) {

        // split으로 String 배열 사용 시 효율성 0점 > charAt() 사용

        Stack<Character> stack = new Stack<>();
        
        for (int i = 0 ; i < s.length() ; i ++) {
            
            if (s.charAt(i) == '(') { // 여는 괄호일 경우 stack에 push
                stack.push(s.charAt(i));
            } else { // 닫는 괄호일 경우 pop
                
                if (stack.isEmpty()) { // stack에 열린 괄호가 없으면 바로 false 반환
                    return false;
                }
                
                stack.pop();    
                
            }
        }

        return stack.isEmpty();
    }
}

 

결과