Leetcode - 20. Valid Parentheses - Easy

이번 문제는 여는 괄호와 닫는 괄호의 쌍이 맞는지 안 맞는지 구별해 내는 문제입니다.

 

 

괄호는 () [] {} 이렇게 세 종류 입니다.

우선 로직을 생각하기 위해서 패턴을 생각해 보겠습니다.

 

((())), (){()}[[{()}]]

이렇게 되면 true 입니다. 여는 괄호와 닫는 괄호 다 제대로 짝이 맞으니까요.

 

(], (({[{})]))

이런 식으로 되면 false 입니다. 4번째 [ 의 짝이 ) 으로 돼 있어서 맞지 않습니다.

 

여기서 패턴을 생각해 볼 수 있습니다.

1. 여는 괄호 일 때는 true , false를 생각 할 필요가 없다.

2. 첫번째 닫는 괄호가 나오면서 가장 가까운 여는 괄호와 짝이 맞아야 한다.

3. 두번째 닫는 괄호가 나오면서 가까운 두번째 여는 괄호와 짝이 맞아야 한다.

4, 5, 6 ......

 

1번과 2번 패턴까지는 쉽게 로직이 완성 될 것 같은데 3번 서 부터는 좀 복잡해 집니다.

그러면 2번에서 패턴을 다 만족할 수 있도록 로직을 만들 필요가 있습니다.

 

항상 가장 가까운 여는 괄호와 비교 하도록 만들면 됩니다.

그렇다면 한번 짝이 맞는다고 검증되면 그 여는 괄호를 없애면 다음 닫는 괄호는 다시 가장 가까운 여는 괄호와 비교하면 됩니다.

 

그렇다면 패턴은 아래와 같이 정리 될 수 있다.

1. 여는 괄호 일 때는 true , false를 생각 할 필요가 없다.

2. 첫번째 닫는 괄호가 나오면서 가장 가까운 여는 괄호와 짝이 맞아야 한다.

3. 2번에서 짝이 맞으면 해당 여는 괄호를 없애고 1번과 2번을 반복한다.

4. 2번에서 짝이 안 맞으면 false를 반환한다.

5. 모든 짝이 맞으면 true를 반환한다.

 

이제 이 패턴을 만족시키는 로직을 만들 차례다.

우선 어떤 API 메소드를 사용할 지 생각해 보자.

여는 괄호를 쌓다가 짝이 맞으면 하나씩 없앨 것이다.

 

그렇다면 Stack을 사용해서 push()와 pop()메소드들을 사용하면 된다.

IsEmpty()를 사용해서 마지막에 체크를 하면 된다.

 

https://docs.oracle.com/javase/7/docs/api/java/util/Stack.html

Stack (Java Platform SE 7 )

 

 

그 다음에는 여는 괄호와 닫는 괄호의 맞는 쌍을 비교해야 되니까 Map을 사용하면 좋을 것 같다.

 

https://docs.oracle.com/javase/8/docs/api/java/util/Map.html

Map (Java Platform SE 8 )

 

이것을 통해서 만든 코드와 output은 아래와 같다.

 

어떻게 작동하는 지 보기 위해 여기저기 로그를 프린트 하도록 했다.

입력값은 "(()){}[{())]" 이다.

그리고 stdout 을 보면 아래와 같다.0 c is (
1 c is (
2 c is )
2 open is (
*** 2 open is (, c is )
3 c is )
3 open is (
*** 3 open is (, c is )
4 c is {
5 c is }
5 open is {
*** 5 open is {, c is }
6 c is [
7 c is {
8 c is (
9 c is )
9 open is (
*** 9 open is (, c is )
10 c is )
10 open is {
*** 10 open is {, c is )

 

처음 두 열린 괄호는 stack에 넣는다. 처음으로 닫힌 괄호 )가 나왔다.바로 직전 열린 괄호를 보니 ( 여서 짝이 맞는다. 그러면 통과하고 해당 (는 stack에서 제외한다.그 다음도 닫힌 괄호 ) 있고 직전 열린 괄호는 ( 이니 통과하고 해당 (는 stack에서 제외 한다.(()) 부분은 검증이 다 끝났고 현재 Stack에는 아무 것도 없다. 그 다음 { 는 스택에 넣고 그 다음을 보니 } 이므로 짝이 맞으니까 통과하고 {는 스택에서 제외.{}도 검증 됐고 Stack에는 아무것도 없는 상태 

 

입력값 중에서 [{())] 를 검증해야 한다.[ 는 열린 괄호이니 스택으로, 그리고 { 도  스택으로 그리고 ( 도...이제 스택에는 [{( 가 있다.다음은 닫힌 괄호 ) 이다. 보니까 가장 가까운 열린 괄호는 ( 이니까 짝이 맞다. 그러면 통과 하고 (는 스택에서 제외.이제 스택에는 [{ 가 있다.다음을 보니까 닫힌 괄호 ) 이다. 스택에는 { 이 있다.짝이 맞지 않으니까 여기서 이 입력값은 invalid 판정이 나게 된다.그래서 결과는 false.

 

전체 코드를 보면 아래와 같다.

class Solution {

    private static final Map<Character, Character> map 

        = Map.of('(', ')',

                 '{','}',

                 '[',']');

    

    public boolean isValid(String s) {

        Stack<Character> stack = new Stack<>();

        for(char c : s.toCharArray()) {

            if(map.containsKey(c)) {

                stack.push(c);

            } else {

                if(stack.isEmpty()) {

                    return false;

                }

                char open = stack.pop();

                if(map.get(open) != c) {

                    return false;

                }

            }

        }

        return stack.isEmpty();

    }

}

 

우선 (),[],{} 쌍을 Map에 넣는다.

그리고 isValid 안에서 Stack을 만든다.

입력된 스트링의 아이템 갯수 만큼 for 문을 돌린다.

 

해당 아이템이 Map의 key 이면, 즉 열린 괄호이던 stack 에 push 한다.

Key 가 아니면 stack에 있는 key와 짝이 맞는지 비교한다. Stack이 비어 있거나 짝이 맞지 않으면 false를 반환한다.

 

For 문을 다 돌고 나서 stack에 아무 값도 없으면 모든 짝이 다 맞는 것이니까 입력값은 Valid하고 true를 리턴한다.