[JAVA] [LEVEL2] 프로그래머스 - 올바른 괄호

프로그래머스 programmers Level2 올바른 괄호 - java 자바

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/12909

프로그래머스

 

[풀이]

처음 문제만봐서는 간단하다고 생각했는데, 생각보다 시간이 소요됐다. 스택으로 풀었을때 답은 맞았는데, 효율성 2번에서 계속 시간초과되는 문제가 있었다.

우선 문제를 풀며 겪었던 시행착오들을 기록해둔다. 조건을 여러개 수정해가며 시간을 줄이려고 노력했었다.

1. s.split("") 으로 문자열을 잘라서 String[] 을 취득했는데, s.toCharArray() 을 이용해서 char[] 을 취득하는 것이 빠르다.
   👉 String 에서 char 로 변환하는 과정에서 또 하나 개선된 점은, String.valueOf() 를 이용하여 문자열을 비교하는 과정을 거쳤었는데, char 를 사용함으로써 이를 사용하지않고 == 비교를 사용하도록 바꿨다.
2. for 문으로 char[] 배열을 순차적으로 확인해야 하므로 for 문을 돌리기 전에 확인후 삭제할 수 있는 케이스들을 먼저 체크했다.
   👉시작이 ) 또는 끝이 ( 또는 전체 길이가 홀수면 불완전 괄호이므로 바로 false 리턴해주었다.

위의 과정을 통해 시간을 줄일 수 있었으나, 효율성 2번에서 여전히 시간초과되는 문제가 있었다.

 

그래서 Stack 을 과감히 제거했다.  먼저 스택을 사용하는 방법은 스택의 맨 위에 있는 값을 확인해서 괄호 짝이 맞으면 스택에서 제거해주는 코드로 작성했었다.

 

(참고) Stack 을 사용하는 코드

char[] chars = s.toCharArray();
Stack<Character> stack = new Stack<>();
// 1. 스택이 비어있지 않음 and 맨 위 값이 ( && 현재 값이 ) 이면, 괄호 한쌍이므로 스택에서 삭제
if (!stack.empty() && ROUND_OPEN == stack.peek() && ROUND_CLOSE == chars[i]) {
    stack.pop(); // 한 쌍 () : OK
    
// 2. 스택이 비어있지 않음 and 맨 위 값이 ) && 현재 값이 ( 이면, 부정괄호 이므로 false 리턴
} else if (!stack.empty() && ROUND_CLOSE == stack.peek() && ROUND_OPEN == chars[i]) {
    return false; // 부정괄호 )( : NG

// 3. 그 외이면 스택에 값을 넣는다.
} else {
    stack.push(chars[i]);
}

👉 이렇게 작성하면 매번 스택에서 peek(), pop() , push() 등의 메소드를 실행해야 하므로 효율성 테스트를 통과하기위해 스택을 과감히 삭제하는 방향으로 전환했다.

 

기본적인 풀이방법은 같지만 Stack 대신, int 를 이용하여 "(" 괄호수를 카운트하고, ")" 으로 쌍이 맞으면 카운트를 -1 해주는 방향으로 바꿨다.

매번 스택의 메소드를 사용하지않고 += 1 , -= 1 , == 연산만으로 확인하므로 속도가 개선되었다.

문제 분류가 스택/큐로 되어있어 Stack 을 사용해야만 한다는 생각에 완전히 매몰되어 있었다.

스택을 사용하니 효율성 2번에서 시간초과가 발생하여 해결까지 시간이 오래걸렸다.

그래서 스택을 이용할때의 개념을 이용하되, Stack 대신 int 로 카운트 하는 방식을 택했다.

 

[java 코드]

private final static char ROUND_OPEN = '(';
private final static char ROUND_CLOSE = ')';

/**
 * 올바른 괄호
 * @param s '(' 또는 ')' 으로 이루어진 문자열
 * @return '()'으로 짝지어져 올바른 괄호이면 true, 아니면 false
 *
 */
public boolean solution(String s) {
    boolean answer = true;
    char[] chars = s.toCharArray();
    int openCount = 0;
    // 시작이 ) or 끝이 ( or 괄호갯수 홀수 이면, false
    if (ROUND_CLOSE == chars[0] || ROUND_OPEN == chars[chars.length - 1] || chars.length % 2 != 0) {
        return false;
    } else {
        for (int i = 0; i < chars.length; i++) {
            // ( 이면 카운트 +1
            if (ROUND_OPEN == chars[i]) {
                openCount++;
            } else {
                // ) 이면 쌍을 확인한다.
                if (openCount < 1) { // ( 괄호 수가 1 미만이면
                    // 여는 괄호없이 바로 닫는 괄호가 나오는 것이므로 false
                    return false;
                }
                // ( 괄호 수가 1 이상이면, 닫는 괄호와 쌍이 맞으므로 카운트 -1
                openCount--;
            }
        }
    }
    // s 전체 길이가 짝수 and ( 갯수가 짝수로 끝나는 경우 [예] (())((
    if (openCount > 0) {
        // 닫는 괄호가 없으므로 false
        return false;
    }
    return answer;
}