LeetCode 20번 - Valid Parentheses

문제 들여다보기

괄호로 이루어진 문자열이 주어지며, 문자열 내에서 괄호가 정상적으로 사용되었는지 판단해 true 또는 false를 반환하는 문제이다.

 

괄호가 정상적으로 사용되었는지를 판단하는 규칙은 다음과 같다!

 

1. 모든 괄호는 먼저 열린 후에 닫혀야 한다.

2. 괄호를 열고 닫을 때 그 짝이 같아야 한다.

3. 서로 다른 종류의 괄호가 교차되어선 안된다!

 

예를 들어, 문자열이 " ] ( ) { } "인 경우 1번 규칙에 어긋난다.

만약 주어진 문자열이 " ( } " 인 경우, 2번 규칙에 어긋나며,

주어진 문자열이 " [ { ] } ( ) "인 경우, 3번 규칙에 어긋난다. 

 

규칙에 어긋나면 결과로 false를 반환해야 한다.

 

 

---

생각의 흐름

처음에는 숫자, 문자를 단순 비교할 때처럼 이중반복문으로 풀려고 했었다.

 

그러나 이중반복문으로 풀려고 하니 코드가 길고 복잡해졌고, 계속해서 조건을 추가해야 했다.

결정적으로 "( [ [ [ [ [ ] ] ] ) " 이런 식으로 생긴 문자열은 제대로 판단하지 못했다.

 

조건을 추가하고 추가하면 언젠가는 해결할 순 있겠지만... 좋은 방법이 아니라고 생각해 처음부터 다시 풀었다.

 

한참을 씨름하다 결국 힌트를 봤는데.. 자료 구조를 활용하고, 후입선출법으로 처리된다는 사실을 기억해야한다는 내용이 적혀있었다.

 

 

 

---

풀어보기

아직 자료 구조에 대해서 아는 것이 거의 없어서... 우선 기존에 알고 있던 리스트를 사용하기로 했다.

 

처음 사용한 방식은 다음과 같다.

 

1. 괄호를 저장할 List를 선언한다. ArrayList를 사용했다.

2. 주어진 문자열의 길이가 홀수인지 검사한다. 홀수이면 검사할 필요가 없으므로 false를 반환한다.

3. 홀수가 아니면 반복문으로 전체 문자열을 순차적으로 검사한다.

4. 여는 괄호(  ' ( ', ' [ ', ' { ' ) 를 만나면 해당 괄호를 ArrayList의 맨 앞에 추가한다.

 

5. 닫는 괄호(  ' ) ', ' ] ', ' } ' ) 를 만나면 ArrayList의 맨 앞 문자를 확인한다.

5-1. 만약 ArrayList가 비어있으면, 괄호가 열린 적이 없으므로 false를 반환한다.

5-2. 만약 ArrayList의 맨 앞 문자가, 4번에서 만난 닫는 괄호와 짝이 맞지 않으면 false를 반환한다.

 

6. 검사가 끝난 후, ArrayList를 확인한다.

6-1. 만약 ArrayList가 비어있지 않다면, 열린 후 닫히지 않은 괄호가 있는 것이므로 false를 반환한다.

 

작성한 코드의 전문은 다음과 같다.

boolean isValid = true; // 결과값을 저장할 변수로, true라고 가정하고 시작했다.
ArrayList brackets = new ArrayList(); // 여는 괄호를 저장할 리스트이다.

if(s.length() % 2 != 0) { // 문자열의 길이가 홀수면 검사할 필요가 없어서 먼저 걸러냈다.
    isValid = false;
} else {
    for(int i=0; i<s.length(); i++) {
        char ch = s.charAt(i);
        
        // 현재 인덱스의 문자가 여는 괄호면, 리스트의 맨 앞에 해당 문자를 저장한다.
        if(ch=='(' || ch=='[' || ch=='{'){
               brackets.add(0, ch);
               
        } else {// 현재 인덱스의 문자가 닫는 괄호면, 리스트와 대조한다.         
            if(!brackets.isEmpty()){  // 리스트가 비어있지 않을 때만 검사한다.
                char pair = (char)brackets.get(0);
				
                // 여는 괄호와 닫는 괄호 짝이 맞으면 리스트의 맨 앞에 있는 문자열을 제거한다.
                // 짝이 맞지 않으면 결과 변수에 false를 대입한다.
                
                if(ch == ')') {
                    if(pair == '(') brackets.remove(0);
                    else isValid = false;
                }
                if(ch == ']') {
                    if(pair == '[') brackets.remove(0);
                    else isValid = false;
                }
                 if(ch == '}') {
                    if(pair == '{') brackets.remove(0);
                    else isValid = false;
                }       

            } else { 
            	// 리스트가 비어있는 경우, 괄호가 열리지 않았으므로 
            	// 결과 변수에 false를 대입한다.
                isValid = false;
            }
        }
		
        // 결과 변수가 false이면 더 이상 검사할 필요가 없으므로 반복문을 종료한다.
        if(!isValid) break;
    }
}

// 모든 검사가 끝난 후, 리스트가 비어있지 않으면 닫히지 않은 괄호가 있다는 뜻이므로
// 결과 변수에 false를 대입한다.
if(!brackets.isEmpty()) {
    isValid = false;
}

return isValid;

 

이렇게 작성해서 제출하자 잘 처리되었다.

 

그러나 속도, 메모리 사용량 등 결과가 마음에 들지 않아 다른 방법을 찾아보기로 했다.

 

예전에 컬렉션에 대해서 공부할 때, 컬렉션에서 값을 제거하면서 동시에 해당 값을 반환할 수 있는 함수를 가진 컬렉션이 있었던게 생각나서 찾아보다가 stack을 알게 되어 stack을 사용해서 문제를 다시 풀어보았다.

 

---

풀어보기2

stack은 데이터를 저장할 때, 마지막에 저장한 데이터가 가장 위에 위치하게 된다.

데이터를 꺼내면, 마지막에 저장한 데이터가 꺼내지게 된다. 즉 후입선출법이 적용된다.

 

또한 stack에는 .pop()이라는 메서드가 있다.

이 메서드는 stack의 가장 마지막 데이터를 꺼내서 반환한다.

 

이 때, 마지막에 있는 데이터를 stack에서 제거하면서 동시에 그 값을 반환해주므로

리스트를 사용할때처럼 값을 꺼내고, 삭제하는 작업을 별도로 할 필요가 없다.

 

사용한 방법은 다음과 같다.

 

1. 괄호를 저장할 stack을 선언한다.

2. 주어진 문자열의 길이가 홀수인지 검사한다. 홀수이면 검사할 필요가 없으므로 false를 반환한다.

3. 홀수가 아니면 반복문으로 전체 문자열을 순차적으로 검사한다.

4. 여는 괄호(  ' ( ', ' [ ', ' { ' ) 를 만나면 해당 괄호를 stack에 추가한다.

 

5. 닫는 괄호(  ' ) ', ' ] ', ' } ' ) 를 만나면 stack이 비어있는지 확인한다. 

5-1. stack이 비어있으면 괄호가 열린 적이 없으므로 false를 반환한다.

5-2. stack이 비어있지 않으면, pop()메서드를 사용해 stack의 마지막 값을 꺼내서 현재 인덱스의 문자와 비교한다.

짝이 맞지 않으면 false를 반환한다.

 

6. 검사가 끝난 후, stack을 확인한다.

6-1. 만약 stack이 비어있지 않다면, 열린 후 닫히지 않은 괄호가 있는 것이므로 false를 반환한다.

6-2. stack이 비어있다면 true를 반환한다.

 

 

작성한 코드의 전문은 다음과 같다.

boolean isValid = true;
Stack<Character> stack = new Stack<>();

if(s.length() % 2 != 0) {
    isValid = false;
} else {
    for(int i=0; i<s.length(); i++) {
        char ch = s.charAt(i);
        if(ch=='(' || ch=='[' || ch=='{'){
        	   // 여는 괄호를 만나면 값을 stack에 추가
               stack.push(ch);
        } else {
            if(!stack.isEmpty()){
            	// 닫는 괄호를 만났고
                // stack이 비어있지 않다면 stack에서 마지막 데이터를 꺼낸다.
                char lastCh = stack.pop();

                if(ch == ')') {
                    if(lastCh != '(') isValid = false;
                }
                if(ch == ']') {
                    if(lastCh != '[') isValid = false;
                }
                if(ch == '}') {
                    if(lastCh != '{') isValid = false;
                }     

            } else {
            	// 닫는 괄호를 만나긴 했으나
                // stack이 비어있으면 즉시 false를 반환한다.
                isValid = false;
            }
        }

        if(!isValid) break;
    }
}       

if(!stack.isEmpty()) {
    isValid = false;
}

return isValid;

 

위처럼 작성하여 제출했다!

 

---

제출 결과 잘 처리되었지만, 속도와 메모리 사용량이 마음에 들지 않아

 

결과를 저장하던 변수 'isValid'를 별도로 만들지 않고 바로바로 값을 반환하게 바꾸었다.

 

 

최종적으로 작성한 코드는 다음과 같다.

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

if(s.length() % 2 != 0) {
    return false;
} else {
    for(int i=0; i<s.length(); i++) {
        char ch = s.charAt(i);
        if(ch=='(' || ch=='[' || ch=='{'){
               stack.push(ch);
        } else {
            if(!stack.isEmpty()){
                char lastCh = stack.pop();

                if(ch == ')') {
                    if(lastCh != '(') return false;
                }
                if(ch == ']') {
                    if(lastCh != '[') return false;
                }
                if(ch == '}') {
                    if(lastCh != '{') return false;
                }     

            } else {
                return false;
            }
        }

    }
}       

if(!stack.isEmpty()) {
    return false;
} else {
    return true;
}

 

제출 결과 속도, 메모리 사용량, 코드 길이 등 모든 부분이 개선되었다!

 

stack 외에도 다른 자료구조가 많이 있으므로 더 공부해야겠다...