Programmers / Level 2 / 올바른 괄호

[문제 설명]

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어

• "()()" 또는 "(())()" 는 올바른 괄호입니다.
• ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.

'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

[제한사항]

• 문자열 s의 길이 : 100,000 이하의 자연수
• 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

[입출력 예]

s	answer
"()()"	true
"(())()"	true
")()("	false
"(()("	false

 

---

 

비슷한 문제를 백준에서 풀었던 기억이 있었다.

지금 찾아보니, 그 땐 Stack으로 이번엔 Queue로 풀었다는 점만 다른 것 같다.

 

문제를 설명하자면, '(' 문자로 열린 경우, 짝지어서 ')' 로 닫혀야 한다

그래서 잘 생각을 해보면, 굳이 모든 문자를 다 넣고 검사를 할 이유가 없다.

 

'(' 문자가 나온 경우에만 큐에 넣고,

')' 문자가 나온 경우엔 큐에서 빼준다. 여기서 주의할 점은, 만약 큐가 비어있는데 ')' 문자를 빼려고 하는 경우엔 오류이므로, flag를 바꿔주고 바로 정답을 출력해주면 된다.

 

그렇지 않은 경우엔 위 과정을 반복해주고, for문이 끝났을 때

큐에 남은 문자가 있다면 (!queue.isEmpty()) 올바른 괄호가 아니므로 (짝이 없으니까) false를 출력해준다.

 

전의 풀이에서는 스택을 사용했기 때문에 제일 나중에 넣은 것을 빼주지만, 큐에서는 queue.remove로 가장 앞의 값을 제거한다.

어차피 남은 개수로만 따지면 정답이 나오기 때문에, 무엇을 사용하든 상관은 없다고 생각된다.

 

import java.util.LinkedList;
import java.util.Queue;

class Solution {
     boolean solution(String s) {
        boolean flag = true;
        
        Queue<Character> queue = new LinkedList<>();
        for(int i=0; i<s.length(); i++) {
            char c = s.charAt(i);

            if(c == '(') {
                queue.add(c);
            }
            if(c == ')') {
                if(queue.isEmpty()) {
                    flag = false;
                    break;
                }
                queue.poll();
            }
        }

        if(!queue.isEmpty()) flag = false;

        return flag;
    }
}

 

---

 

비슷한 문제 (백준 9012 괄호 문제)

: https://gr616.tistory.com/298