프로그래머스 Lv.2) 올바른 괄호 짝지어 제거하기

올바른 괄호 짝지어 제거하기

코딩테스트 연습 - 짝지어 제거하기

풀이

로직을 바꿔가며 세 번 시도한 문제다.

첫번째는 StringBuffer에 주어진 String을 두고, 겹치는 부분을 계속해서 지워나가고 StringBuffer의 길이가 0이면 1, 아니면 0을 리턴해주었는데, 역시나 시간초과가 떴다.

두번째로 시도한 로직은 먼저 String을 돌면서 연속되는 글자가 있는 두 index를 LinkedList에 넣어주었다. LinkedList를 돌면서 카운팅을 해주었고, 해당 문자를 제거하고 나서 좌 우로 같은 문자가 존재하면 LinkedList에 넣어주었는데, 내 생각에는 정답이라고 생각했지만 45점밖에 나오지 않았다. 이후에 여러번 수정을 해봐도 45점에서 고정이었다..

그래서 마지막으로 작성한 코드는 Stack을 이용하는 것이었다. 사실 두번째 로직까지 하고 질문하기 탭을 봤는데 나와 같은 사람이 없었다. 그래서 다른 사람들이 무얼 질문했는지 보다가 Stack을 이용했는데 틀린다는 질문?을 보고, 아 맞다.. 스택... 하며 스택을 쓰기로 했다.

결론적으로는 정말 쉬운 문제다. 예전같았으면 아마 바로 풀었을 문제다. 요즘 복잡한 알고리즘 문제에 대해 고민하거나 점화식을 세우는 연습을 해서 그런지, 복잡하게 풀려고만 하는 것 같다. 다 내려놓고 생각하면 정말 쉬운 문제였다.

 

1. 문자열을 돌면서 스택이 비어있는지 체크한다.

 1-1. 비어있다면 push

2. 비어있지 않다면 스택의 top이 같은 문자인지 확인한다.

 2-1. 같은 문자라면 pop

 2-2. 다른 문자라면 push

3. 스택이 비어있으면 1을, 아니면 0을 리턴

 

코드

import java.util.Stack;

class Solution
{
    public int solution(String s) {
        int answer = 0;
        Stack<Character> stack = new Stack<>();
        
        for(int i=0; i<s.length(); i++) {
            char ch = s.charAt(i);
            if(stack.isEmpty()) {
                stack.push(ch);
            } else {
                if(stack.peek() == ch) {
                    stack.pop();
                } else {
                    stack.push(ch);
                }
            }
        }
        
        return stack.isEmpty() ? 1 : 0;
    }
}