[프로그래머스] 올바른 괄호(Java)

문제

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

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

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

제한사항

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

 

 

 

 

문제해결

'스택'이라는 알고리즘으로 해결 할 수 있다.

• count 변수를 이용하여 '('와 ')'의 개수를 조정합니다.
• '('가 나오면 count를 증가시키고, ')'가 나오면 count를 감소시킵니다.
• 도중에 count가 0보다 작아지는 경우는 '('가 부족한 상황이므로 false를 반환합니다.
• 모든 문자열을 다 검사한 후, count가 0이면 올바른 괄호로 간주하여 true를 반환합니다.

이 코드의 시간 복잡도는 O(n)으로, 제한사항인 100,000 길이의 문자열도 효율적으로 처리할 수 있습니다.

 

부끄럽지만 처음에 제가 문제를 이해를 잘못해서 맨 앞은 '(' 맨 뒤는 ')'로 이루어지면 해결되는 간단한 문제인 줄 잘못 봤었습니다. 다들 헷갈리시지 않기를~

 

 

 

 

코드

class Solution {

    boolean solution(String s) {
       
        //'('의 개수를 카운트
       int count = 0;
        
        for(int i = 0; i < s.length(); i++){
            
            char c = s.charAt(i);
            
            if(c == '('){
                count++; // '('가 나오면 카운트 증가
            }else if(c == ')'){
                count--;
            }
            
            if(count < 0){
                return false; // 짝이 안맞는다는 증거.
            }
           
        }
        
        return count == 0;
    
    }
    
}