[프로그래머스 Lv.2] 올바른 괄호

코딩테스트 연습 - 올바른 괄호

문제 설명

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

예를 들어
"()()" 또는 "(())()" 는 올바른 괄호입니다.
")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.

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

제한사항

• 문자열 s의 길이 : 100,000 이하의 자연수
• 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

풀이

To-Do 리스트

1. 첫번째 값은 넣어주고, 두번째 값부터 List에 들어간 경우
   1-1. 마지막 값이 "(" 이고, 현재 배열 값이 ")" 일 때 List에 들어간 값을 제거.
   1-2. 아닌 경우, List에 현재 배열 값을 추가.
2. List의 size가 0인 경우에는 1번을 실행하지 않고 List에 현재 배열 값을 추가.
3. size가 0인 경우에는 true, 아닌 경우에는 false를 출력.

결과

import java.util.*;

class Solution {
    boolean solution(String s) {
        boolean answer = true;
        String[] srr = s.split("");
        List<String> stack = new ArrayList<String>();
        
        stack.add(srr[0]);
        for(int i = 1; i < srr.length; i++){
            if(stack.size() != 0){
                if(stack.get(stack.size()-1).equals("(") && srr[i].equals(")")){
                    stack.remove(stack.size()-1);
                }else {
                    stack.add(srr[i]);
                }   
            }else {
                stack.add(srr[i]);
            }
        }
        answer = stack.size()==0?true:false;
        
        return answer;
    }
}

알게 된 점

정확도 테스트에서는 문제가 없었으나, 효율성 테스트를 통과 하지 못했다.

• 효율성 테스트1 통과 : 한글자씩 체크하기 때문에 str.split("")로 String배열화 하여 사용하는 것보다 str.toCharArray()로 char배열을 사용하는것이 유리.
• 효율성 테스트2 통과 : 무조건 stack에 넣는게 아니라, '(' 보다 ')'가 먼저 나오는 경우는 무조건 false이기 때문에 굳이 for문을 다 돌지 않아도 된다.

import java.util.*;
class Solution {
    boolean solution(String s) {
        boolean answer = true;
        char[] crr = s.toCharArray();
        Stack<Character> stack = new Stack<Character>();
        for(int i = 0; i < crr.length; i++){
            if (crr[i] == '(') stack.push(crr[i]);
            else {
                if(stack.empty()) return false;
                else stack.pop();
            }
        }
        answer = stack.empty();
        return answer;
    }
}