[99클럽 코테 스터디] 8일차 TIL 스택/큐

 

 

오늘의 문제는 프로그래머스

 

 

올바른 괄호 

 

 

문제

 

 

 

문제 접근 및 풀이 과정

오늘의 문제는 주어진 문자열에서 괄호가 올바르게 짝지어져 있는지를 검사하는 문제였습니다. 

권장 풀이 시간은 30분이었고, 저는 36분이 걸렸습니다.

오늘 문제의 키워드는 스택/큐 였기 때문에 저는 둘 중 스택을 사용해 문제를 해결해보았습니다. 

 

 

문제 접근 방식

스택을 사용해 괄호의 쌍이 올바른지 검사하는 방식으로 접근했습니다. 먼저 반복문을 통해 문자열을 순회하며 각 문자를 확인합니다. 열린 괄호는 스택에 추가하고 닫힌 괄호는 제거한 뒤 최종적으로 스택이 비어있지 않으면 false를, 그렇지 않으면 true를 반환하도록 설계했습니다. 

 

 

문제 풀이

import java.util.Stack; 

class Solution {
    boolean solution(String s) {
        
        boolean answer = true;

        Stack<Character> stack = new Stack<>();
        
        for(int i = 0; i<s.length(); i++) {
            char ch = s.charAt(i);
            
            if(ch == '(') {
                stack.push(ch);
            } 
            
            else if(ch == ')') {
                if(stack.isEmpty()) {
                    return false; 
            } 
            else {
                stack.pop(); 
            }
        }
    }
        if (!stack.isEmpty()) {
            answer = false; 
        }
    

        return answer;
    }
}

 

 

스택을 사용한 이유는? 

스택은 LIFO 방식의 자료구조로, 데이터를 추가하고 삭제하는 데 효율적입니다. 따라서 이 문제처럼 유효성 검사를 하는데 적합한 자료구조 입니다. 스택을 사용하면 열린 괄호를 만날 때마다 스택에 추가하고, 닫힌 괄호를 만날 때는 스택에서 데이터를 제거하여 짝이 맞는지 쉽게 확인할 수 있습니다. 

 

 

유효성 검사 

문자열의 각 문자를 검사한 뒤 최종적으로 스택이 비어있는지 isEmpty() 메서드로 확인하여 스택이 비어 있으면 모든 괄호가 올바르게 짝지어져 있다는 것이니 true를 반환하고, 그렇지 않으면 false를 반환합니다. 

 

리팩토링 

 

처음 작성한 코드는 스텍의 장점을 활용하지 않아 비효율적이었고, 가독성도 떨어졌습니다. 모든 문자를 스택에 넣은 다음 스택의 pop() 메서드를 사용해 문자의 개수를 세는 방식이었는데, 이는 매우 비효울적 이었습니다. 따라서 리팩토링을 통해 위와 같이 열린 괄호 문자만 스택에 추가하고, 닫힌 괄호가 나오면 스택에서 제거하는 방식으로 수정했습니다. 이를 통해 코드의 효율성 및 가독성을 개선할 수 있었습니다. 

 

 

 

 

 

 

이렇게 오늘 8일차 TIL을 작성해 보았습니다.