문제 출처

프로그래머스 코딩테스트 연습 > 스택/큐 > 올바른 괄호
https://school.programmers.co.kr/learn/courses/30/lessons/12909

문제 설명

괄호로 이루어진 문자열 s( ex : "()()" , ")()(" ) 가 주어질 때, s는 '(' 와 ')'의 짝이 잘 지어있는가에 대해서 올바른 괄호는 true, 아닐 경우 false를 return 하는 문제이다.

접근 방법

처음 접근할 때, 해당 문제의 경우를 3가지로 분류했다.
1) 정상일 경우
2) ')'로 시작할 경우
3) 비정상일 경우( 괄호 짝의 수가 안맞을 경우)

하지만 문제를 풀다 보니 이와 같이 접근하면 비정상일 경우가 더 있다는 것을 파악했다.
그래서 접근하는 방법으로, 일단 큐에 다 넣고, 큐의 가장 맨 앞이 ')' 인 경우 false를 return한다. 아닌 경우에는 큐의 head와 그에 상응하는 ')' 를 하나 지운다.

import java.util.*;

class Solution {
    boolean solution(String s) {
        boolean answer = true;
        
        Queue q = new LinkedList();
        for(int i=0;i<s.length();i++){
            q.add(s.charAt(i));
        }
        
        while(q.isEmpty()){
            if(q.peek().equals(')')) { 
                answer = false;
            return answer;}
            else{
                q.remove();
                q.remove(')');
            }
            
        }

        return answer;
    }
}

하지만 이는 시간 복잡도가 O(n^2)으로 효율성 점수에서 좋은 점수를 받지 못했다.( 50/100 )

그래서 다른 접근 방법으로, 큐에서 ')'를 찾아서 시간 복잡도를 늘리지 않고, count 변수를 이용해서 '(' 가 있다면, count를 1증가 시키고, ')'가 있다면, count를 1감소 시키는 방향으로 접근했다. 이를 통해 count가 음수 값이 되면 false를 return 하고, 최종적으로 count가 0인가에 따라서 true / false 값을 return 하는 방식으로 접근했다.

import java.util.*;

class Solution {
    boolean solution(String s) {
        boolean answer = true;
        int count = 0;
        
        Queue q = new LinkedList();
        for(int i=0;i<s.length();i++){
            q.add(s.charAt(i));
        }
        
        while(!q.isEmpty()){
            if(q.remove().equals(')')){
                count--;
                if(count <0){
                    answer = false;
                    return answer;
                }
            }
                else{
                    count++;
                }
            }
        return count ==0;
        }
    }

( 100 / 100)

알게된 점

count 변수를 사용해서 접근하게 되면, '(' 가 나왔을 때, '('에 상응하는 ')'를 찾기 위해서 큐를 다시 순회하지 않아도 되기 때문에 시간 복잡도를 아낄 수 있다.

% 결국 100점을 받을 수 있는 풀이 방법은 블로그 및 GPT를 찾아보면서 알게 되었다. 나중에는 혼자 오답노트를 작성할 수 있으면 한다.

문제푼 흔적