[프로그래머스] 12909 올바른 괄호 - Java

📌 문제 정보

• 출처: 문제 링크
• 난이도: ⭐
• 문제 유형: 스택 / 큐
• 사용 언어: Java

---

🔍 문제 설명

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

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

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

제한사항

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

---

💡 풀이 노트

💡 문제 핵심
1. 왼쪽 괄호와 오른쪽 괄호의 개수를 각각 센다.
2. 순차적으로 문자열을 탐색하며,
    - `')'`가 `'('`보다 먼저 많아지면 즉시 `false`.
3. 탐색이 끝난 후,
    - `'('`와 `')'`의 개수가 다르면 `false`. 

 

<`false`가 나오는 경우>

1. 닫는 괄호가 먼저 나올 때

( ) )  → 불가능 ❌

닫는 괄호가 더 많아졌기 때문에 `rightCnt > leftCnt` 조건에서 걸림

for(int i = 0 ; i < s.length(); i++){
	char c = s.charAt(i);
	if(c == '(')
		leftCnt++;
	else
		rightCnt++;
	if(rightCnt > leftCnt) return false;
}

 

2. 괄호 개수가 안 맞을 때

( ( ) (  → 불가능 ❌

전체를 다 봤더니 `leftCnt != rightCnt`

if(leftCnt != rightCnt) return false;

---

🚀 코드 (Java)

class Solution {
    boolean solution(String s) {
        boolean answer = true;
        int leftCnt = 0; // 왼쪽 괄호의 수
        int rightCnt = 0; // 오른쪽 괄호의 수
        
        for(int i = 0 ; i < s.length(); i++){
            char c = s.charAt(i);
            if(c == '(')
                leftCnt++;
            else
                rightCnt++;
            if(rightCnt > leftCnt) return false;
            
        }
        if(leftCnt != rightCnt) return false;

        return answer;
    }
}

---

🖥 실행 결과

입력 & 출력

"()()"		true
"(())()"	true
")()("		false
"(()("		false

 

---

🔄 개선 가능성

• `Stack`을 이용
  • 왼쪽 괄호가 나오면 스택에 넣는다.
  • 오른쪽 괄호가 나오면 스택에서 왼쪽 괄호를 하나 뺀다.
  • 스택이 비었으면, `False` 반환한다.
  • 모두 검사했는데, 스택이 비었으면 `True`를 반환하고, 그렇지 않으면 `False`를 반환한다.
• 모두 검사했는데, 스택이 비었으면 `True`를 반환하고, 그렇지 않으면 `False`를 반환한다.

---

📌 깃허브 코드 저장소: https://github.com/glorypang/CodingTest