반응형
블로그 이미지
개발자로서 현장에서 일하면서 새로 접하는 기술들이나 알게된 정보 등을 정리하기 위한 블로그입니다. 운 좋게 미국에서 큰 회사들의 프로젝트에서 컬설턴트로 일하고 있어서 새로운 기술들을 접할 기회가 많이 있습니다. 미국의 IT 프로젝트에서 사용되는 툴들에 대해 많은 분들과 정보를 공유하고 싶습니다.
솔웅

최근에 올라온 글

최근에 달린 댓글

최근에 받은 트랙백

글 보관함

카테고리

Leetcode - 20. Valid Parentheses - Easy

2022. 8. 14. 01:16 | Posted by 솔웅


반응형

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

 

 

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

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

 

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

이렇게 되면 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 )

The Stack class represents a last-in-first-out (LIFO) stack of objects. It extends class Vector with five operations that allow a vector to be treated as a stack. The usual push and pop operations are provided, as well as a method to peek at the top item o

docs.oracle.com

 

 

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

 

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

 

Map (Java Platform SE 8 )

If the specified key is not already associated with a value (or is mapped to null), attempts to compute its value using the given mapping function and enters it into this map unless null. If the function returns null no mapping is recorded. If the function

docs.oracle.com

 

이것을 통해서 만든 코드와 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를 리턴한다.

 

 

반응형