[프로그래머스] (Java) 올바른 괄호 문제풀이 (스택/큐)

 

1. 문제설명

---

2. 접근방식

1) 스택을 사용하지 않고 풀기
문자열을 순회하며 닫힌 괄호와 열린 괄호의 갯수를 변수에 저장하고 개수가 같으면 true, 틀리면 false 를 반환하는 방법
 
2) 스택을 사용하여 괄호의 짝을 맞추는 방법
단순히 생각해서 괄호가 열린 경우 스택에 넣고, 닫힌 괄호가 나오면 스택에서 꺼내는 방식
 

---

3. 문제풀이

3-1. 스택 사용하지 않고 풀기

프로그래머스에서는 큐/스택 카테고리에 있는 문제이지만 굳이 스택을 사용하지 않아도 깔끔하게 풀 수 있는 문제이다. 
처음에는 열린 괄호를 openCnt, 닫힌 괄호를 closeCnt 에 저장해서 그 갯수가 일치하면 true를 반환하는 방식으로 코드를 짰다. 

class Solution {
    boolean solution(String s) {
        int openCnt = 0;
        int closeCnt = 0;
        for(int i = 0; i < s.length(); i++) {
            if(s.charAt(i)=='(') {
                openCnt++;
            } else if(s.charAt(i)==')') {
                closeCnt++;
            }
        }
        if(openCnt==closeCnt) {
            return true;
        } 
        return false;  
    }
}

 

 
 
하지만 내가 짠 코드에 한 가지 문제가 있었다. 테스트 케이스에서 괄호가 ")()("인 경우 열린괄호 갯수 = 닫힌 괄호 갯수가 일치해서 true 값이 반환되었다. 하지만 이 경우 닫힌 괄호가 먼저 시작되었기 때문에 false를 반환해주어야 한다. 이 문제를 해결하기 위해 코드를 손봐주었다. for문 안에서 openCnt가 closeCnt보다 작으면 false를 반환한다는 조건을 하나 더 추가해 주면 간단히 해결되었다.
 

class Solution {
    boolean solution(String s) {
        int openCnt = 0;
        int closeCnt = 0;

        for (int i = 0; i < s.length(); i++) {
            // 열린 괄호가 나오면 openCnt 증가
            if (s.charAt(i) == '(') {
                openCnt++;
            } 
            // 닫힌 괄호가 나오면 closeCnt 증가
            else if (s.charAt(i) == ')') {
                closeCnt++;
            }
            // 닫힌 괄호가 열린 괄호보다 먼저 나오면 잘못된 문자열
            if (openCnt < closeCnt) {
                return false;
            }
        }
        // 반복문이 끝난 후 열린 괄호와 닫힌 괄호 개수가 같아야 유효한 문자열
        return openCnt == closeCnt;
    }
}

 
 
생각 해 보니 위의 코드를 더 간단하게 수정할 수 있는데 openCnt랑 closeCnt를 나눌 필요 없이, 그냥 하나의 변수 cnt에 열린 괄호가 나오면 1 증가하고, 닫힌 괄호가 나오면 1 감소를 해 주어도 된다.

class Solution {
    boolean solution(String s) {
        int cnt = 0;

        for (int i = 0; i < s.length(); i++) {
            // 열린 괄호가 나오면 cnt 증가
            if (s.charAt(i) == '(') {
                cnt++;
            } 
            // 닫힌 괄호가 나오면 cnt 감소
            else if (s.charAt(i) == ')') {
                cnt--;
            }

            // 닫힌 괄호가 열린 괄호보다 먼저 나오면 잘못된 문자열
            if (cnt < 0) {
                return false;
            }
        }
        // 모든 괄호가 짝이 맞으면 cnt가 0이어야 한다.
        return cnt == 0;
    }
}

 
 

3-2. 스택 사용한 코드

괄호가 열린 경우 스택에 넣고, 닫힌 괄호가 나오면 스택에서 꺼내는 방식으로 코드 작성

import java.util.Stack;

class Solution {
    boolean solution(String s) {
        Stack<Character> cnt = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            // 열린 괄호가 나오면 스택에 추가
            if (s.charAt(i) == '(') {
                cnt.push('(');
            } 
            // 닫힌 괄호가 나오면 스택에서 꺼낸다
            else if (s.charAt(i) == ')') {
                // 스택이 비어 있으면 잘못된 괄호 형식
                if (cnt.isEmpty()) {
                    return false;
                }
                // 스택에서 하나 꺼내기
                cnt.pop();
            }
        }
        // 스택이 비어 있으면 모든 괄호가 짝을 이루었다는 의미
        return cnt.isEmpty();
    }
}

 
cnt.isEmpty(); 가 true를 반환한다는 것은 stack에 아무것도 남지 않았다는 것이고, 괄호 짝이 맞는다는 뜻이다. 반면, false를 반환하는 경우 stack에 열린 괄호가 아직 남아 있다는 뜻이다. 
 
만약 닫힌 괄호 열린 괄호보다 더 많은 경우에는 loop안의 if(cnt.isEmpty()) { return false; } 구문에 의해 false를 리턴한다. 
 

---

4. 동일 유형 문제 (스택/큐)

[프로그래머스] (Java) 프로세스 문제풀이 (스택/큐)

[프로그래머스] (Java) 다리를 지나는 트럭 (스택/큐)

[프로그래머스] (Java) 주식가격 (스택/큐)

[프로그래머스] (Java) 기능개발 (스택/큐)

[프로그래머스] (Java) 같은 숫자는 싫어 문제 풀이 (스택/큐)