*20. Valid Parentheses

 

진행할 때 Example 4를 생각 못했다.

첫 번째 풀이는 "String "(" 가 있으면 ")" 존재해야 한다." 는 전제를 가지고 코딩했다.

 

class Solution {
    public boolean isValid(String s) {
        String[] Array = s.split("");
        int cnt = 0;
        
        for( int i=0; i<Array.length; i++ ) {
            // ()
            if( Array[i].equals("(") ) {
                for( int j=0; j<Array.length; j++ ) {
                    if( Array[j].equals(")") ) {
                        cnt++;
                    }
                }
            }
            
            // []
            if( Array[i].equals("[") ) {
                for( int j=0; j<Array.length; j++ ) {
                    if( Array[j].equals("]") ) {
                        cnt++;
                    }
                }
            }
            
            // {}
            if( Array[i].equals("{") ) {
                for( int j=0; j<Array.length; j++ ) {
                    if( Array[j].equals("}") ) {
                        cnt++;
                    }
                }
            }
            
        }
        
        if( cnt == 0 ) {
            return false;
        } else if ( cnt < 0 ) {
            return false;
        } else {
            return true;
        }
        
    }
}

 

이 점은

Example 4 : Input: s = "([)]" / Output: false 

를 고려하지 않았다는 점에서 틀린 풀이다.

 

두 번째 풀이는 첫 번째 풀이에

"같은 형식의 bracket이 이웃하는 경우가 무조건 하나 존재해야 성립한다."

가정하고 작성했다.

 

class Solution {
    public boolean isValid(String s) {
        String[] Array = s.split("");
        int cnt = 0;
        
        for( int i=0; i<Array.length; i++ ) {
            // ()
            if( Array[i].equals("(") ) {
                for( int j=0; j<Array.length; j++ ) {
                    if( Array[j].equals(")") ) {
                        cnt++;
                    }
                }
            }
            
            // []
            if( Array[i].equals("[") ) {
                for( int j=0; j<Array.length; j++ ) {
                    if( Array[j].equals("]") ) {
                        cnt++;
                    }
                }
            }
            
            // {}
            if( Array[i].equals("{") ) {
                for( int j=0; j<Array.length; j++ ) {
                    if( Array[j].equals("}") ) {
                        cnt++;
                    }
                }
            }
        }
        
        // 같은 형식의 bracket이 이웃하는 경우
        if( cnt > 0 && s.indexOf("()") != -1
        		|| cnt > 0 && s.indexOf("[]") != -1
        		|| cnt > 0 && s.indexOf("{}") != -1 ) {
            return true;
        } else {
            return false;
        }
        
    }
}

 

이 경우는

Input : "(){}}{" / Output : false

를 고려하지 않았다는 점에서 틀린 풀이라고 떴다.

 

...

 

임의의 brackets 을 때려박는 문제라서 배열과 전혀 어울리지 않는다.

 

해당되는 문제를 해결하면 다른 문제가 나타난다.

String s = ")({})" (첫 번쨰 인덱스가 ")" 로 시작하는 문제)

String s = "([]){" (마지막 인덱스가 "{" 로 끝나는 문제)

String s = "([]"; (bracket 이 닫히지 않는 문제)

위와 같은 형태로 각기 다른 문제점들이 올라온다. 

 

머리 아프다. 배열, contains, indexOf 로 해결하고자 했는데 방법이 보이지 않는다. 

일단 스택으로 해결하고 나중에 배열로 풀 수 없는지 더 생각해 봐야겠다...

 

 

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<Character>();
		
		for( int i=0; i<s.length(); i++ ) {
			char chr = s.charAt(i);
			if( chr == '(' || chr == '[' || chr == '{' ) {
				stack.push(chr);
			} else if ( chr == ')' && !stack.isEmpty() && stack.peek() == '(' ) {
				stack.pop();
			} else if ( chr == ']' && !stack.isEmpty() && stack.peek() == '[' ) {
				stack.pop();
			} else if ( chr == '}' && !stack.isEmpty() && stack.peek() == '{' ) {
				stack.pop();
			} else {
				return false;
			}
		}
		return stack.isEmpty();
    }
}

 

s 를 한 글자씩 Char 화하여 진행

첫 번째 chr 은 무조건 ( 혹은 [ 혹은 { 으로 시작해야 한다. 그외의 경우 false처리

두 번째 chr 은 첫 번째 chr 이 만약 ( 이 들어왔다면

1) 해당 bracket 을 닫아주는 ) 가 들어왔는지 

2) 현재 쌓여있는 stack 이 비어있지는 않은지

3) stack 의 가장 상단에 ( 가 존재하는지

 

두 번째 chr 으로

1) ( 가 들어가면 stack.push('(') 로 (( 상태

2) ] 가 들어가면 return false

3) ) 가 들어가야지 chr == ')' && !stack.isEmpty() && stack.peek() == '(' 가 전부 성립하므로

stack.pop() -> stack 의 가장 위쪽에 있는 원소의 값이 제거됨

 

이 형태가 훨씬 간단하기는 하다... 

근데 contains 로 풀어 보고 싶다.