유효한 괄호 판별하기 [Java / LeetCode 20]

URL : https://leetcode.com/problems/valid-parentheses/

LeetCode - The World's Leading Online Programming Learning Platform

 

 오늘은 유효한 괄호를 판별하는 방법에 대해 알아보겠습니다. 세계 여러 회사의 화이트보드 코딩테스트에서 단골로 질문하는, 매우 쉬우면서도 기본기를 점검할 수 있는 좋은 문제입니다. 

 

 유효한 괄호(Valid Parentheses)가 무엇인가?

 먼저, 유효한 괄호를 판별하는 알고리즘에 대해 논하기 전에, 유효한 괄호가 무엇인지부터 알아보겠습니다. 어떠한 경우를 "유효한 괄호" 라고 부를까요? 유효한 괄호라는 건 다음과 같은 경우를 의미합니다.

 

1. ( )
2. { }
3. [ ]
4. ( [ ] )
5. ( [ { } ] )
6. { [ ] }
7. { ( ) }

 

 반면 유효하지 않은 괄호라는 것은 다음과 같은 경우를 의미합니다

 

1. (
2. {
3. }
4. { )
5. ] {
6. ( [ ) ]
7. [ } ( )

 사실 괄호라는건 초등학교때부터 밥먹듯이 써 온 개념이기 때문에, 위의 예를 보면서 어떤 경우가 유효한 괄호인지, 유효하지 않은 괄호인지 이미 파악하셨을 것 같습니다. 유효한 괄호이려면 다음 조건은 만족해야 합니다.

 

"열림 괄호가 반드시 먼저 나오고, 그 다음 그에 맞는 적절한 닫힘 괄호가 나와야 한다"

"열림 괄호가 연속으로 등장해도 되지만, 반드시 그 괄호들은 순서대로 적절하게 닫혀야 한다"

 

이상으로, 유효한 괄호가 무엇인지에 대해서 알아보았습니다

 

 유효한 괄호(Valid Parentheses)인지 어떻게 판별하는가?

 어떤 경우가 유효한 괄호인지를 알았으니, 주어진 문자열이 유효한 괄호인지 아닌 지 어떻게 판단하는 지 그 알고리즘을 공부해 보겠습니다. 유효한 괄호인지 판단하는 알고리즘은 스택(Stack)자료구조를 이용하여 구현할 수가 있습니다. 

 

예시를 통해 알아보겠습니다.

 

첫 번째 예시 : ( ) { } 가 유효한 괄호인가?

 

 

 

 

 

 왜 유효한 괄호이려면 반드시 스택이 비어 있어야 할까요? 그 내용은 후술할 4번의 예시에서 알아보도록 하겠습니다!

 

두 번째 예시 : ( [ ] ) 가 유효한 괄호인가?

 역시, 그림을 통해 유효한 괄호인지 여부를 판별하는 순서를 설명하겠습니다.

 

 

 

 

 

세 번째 예시 : ( [ } ) 가 유효한 괄호인가?

 역시, 그림을 통해 유효한 괄호인지 여부를 판별하는 순서를 설명하겠습니다.

 

 

 

 

 이처럼, 중간에 단 한번이라도 쌍이 맞지 않는 닫힘괄호가 나온다면 즉시, 유효하지 않은 괄호문으로 판별됩니다!

네 번째 예시 : ( ) ] 가 유효한 괄호인가?

역시, 그림을 통해 유효한 괄호인지 여부를 판별하는 순서를 설명하겠습니다.

 

 

 

 이처럼, 닫힘괄호가 나왔는데 스택이 비어있다면 유효하지 않은 괄호로 판별됩니다. 왜냐하면, 방금 나온 닫힘괄호에 쌍이 맞는 열림괄호가 없다는 의미이기 때문이입니다. 모든 쌍이 맞아야 유효한 괄호문입니다.

다섯 번째 예시 : [  ] ( 가 유효한 괄호인가?

역시, 그림을 통해 유효한 괄호인지 여부를 판별하는 순서를 설명하겠습니다.

 

 

 

 

이처럼, 주어진 문자열의 탐색이 끝났는데 스택이 비어있지 않다면, 유효하지 않은 괄호로 판별됩니다. 왜냐하면, 스택에 남아있는 열림괄호에 쌍이 맞는 닫힘괄호가 없다는 의미이기 때문 입니다. 모든 쌍이 맞아야 유효한 괄호문입니다.

 

전체 소스코드

 위 그림을 보고 소스를 보시면 이해가 수월하실 것이라고 생각됩니다. 소스코드를 첨부하며 설명을 마치도록 하겠습니다!

 

class Solution {
    public boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        
        // 닫힘괄호에 쌍이 맞는 열림괄호인지 판단하기 위해 Map자료구조 사용
        Map<Character, Character> map = new HashMap<>();
        map.put(')', '(');
        map.put(']', '[');
        map.put('}', '{');

	//주어진 문자열을 하나씩 탐색
        for(char ch : s.toCharArray()) {
        
            // 만약 열림괄호라면 스택에 넣는다
            if(!map.containsKey(ch))
                stack.push(ch);
                
            // 만약 닫힌 괄호가 나왔다면
            else{
            	// 스택이 비어있거나, 
            	// 쌍이 맞지 않는 열림괄호가 스택에서 나온다면 유효하지 않은 괄호문!
                if(stack.isEmpty() || (!stack.isEmpty() && stack.pop() != map.get(ch)))
                    return false;
            }
        }

	// 모든 문자를 탐색한 이후에 스택이 비어있어야 유효한 괄호문이다
        if(stack.isEmpty())
            return true;
        else
            return false;
    }
}