[프로그래머스] 알고리즘 고득점 kit - 올바른 괄호 (Stack/Queue)

문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/12909

 

 

<문제 조건>

•  "(" 로 열렸으면 반드시 짝지어서 ")" 로 닫혀야 올바른 괄호

•  여기서 "( ) ( ( )" 와 "( ) ( ) ) ) ( )" 는 올바르지 않은 괄호

 

<접근 방법>

•  들어온 문자가 "(" 일 경우 저장소에 넣었다가

•  들어온 문자가 ")" 일 경우 저장소에 있는 "(" 와 짝짓기

•  이때 가장 마지막 즉, 최신의 "(" 와 비교하므로 후입선출의 구조

 

•  후입선출을 최대한 활용할 수 있는 Stack 생성

•  저장소에 "(" 가 존재하지 않을 경우에 ")" 가 들어올 경우에 대한 에러처리

 

< +α >

•  startsWith, endsWith 를 활용하여 1차 관문을 생성할 수 있지만

•  해당 조건이 필요 없는 경우에 대한 메모리 낭비 발생 가능성 또한 고려 대상

 

<풀이 로직>

•  문자가 "(" 일 경우 Stack 에 push

•  문자가 ")" 일 경우 가장 최근의 "(" 을 Stack 에서 pop

•  이때 pop 할 문자가 없을 경우 에러 처리(올바르지 못한 괄호)

 

 

Stack 을 사용하지 않을 경우

int 를 사용하여 균형을 조절하여 괄호를 검증할 수 있다

 

---

 

Stack 을 사용한 괄호 검증 로직

import java.util.Stack;

class Solution {
    boolean solution(String s) {
        if(s.startsWith(")")) return false;
        if(s.endsWith("(")) return false;
        
        Stack<Character> stack = new Stack<>();
        
         for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) { // 에러 처리
                    return false;
                }
                stack.pop();
            }
        }
        return stack.isEmpty();
    }
}

 

Stack 을 사용하지 않은 괄호 검증 로직

class WithoutStack {
    boolean solution(String s) {
        
        int balance = 0; 
        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if(c == '(') {
                balance++; 
            } else if(c == ')') {
                balance--; 
                if(balance < 0) { // 에러 처리
                    return false;
                }
            }
        }
        
        return balance == 0;
    }
}