💡 문제

문제설명

🤔 고민사항

• 괄호문제는 전형적인 스택 문제다. 오랜만이긴 했지만 어렵지 않게 풀어 나갔다.
• 다음과 같이 풀이과정을 도출했다.
  배열을 순차적으로 순회하며

1. ")"이 들어올땐 스택에 "("이 있는 경우에만 가능하다. => 즉, 스택이 비어있으면 return false
2. ")"이 들어왔을 때 스택에 "("이 있다면 스택에서 "("를 하나 pop한다.
3. "("이 들어올때는 제약사항이 딱히 없으니 바로 스택에 push한다.
4. 순회가 끝났을때 스택에 "("이 남아있으면 괄호가 올바르지 않은 것이다.

• 처음에는 "(" 스택, ")" 스택 2개의 스택을 두고 풀어야 하는줄 알았는데 생각해보니 "(" 스택만 있으면 된다. 필요에 따라 push, pop, isEmpty() 연산을 하면 되는 것.
• 스택에 꼭 "("을 push할 필요는 없다. 나같은 경우 "("이 들어오면 int 1을 push해서 카운팅 했다.

import java.util.*;

class Solution {
    
    boolean solution(String s) {
        String[] input = s.split("");
        Stack<Integer> stack = new Stack<Integer>();
        
        for(int i=0; i<input.length; i++){
            String now = input[i];
            if(now.equals("(")){
                stack.push(1);
            }else if(now.equals(")")){
                if(stack.isEmpty())
                    return false;
                stack.pop();
            }
        }
        
        if(stack.isEmpty())
            return true;
        else
            return false;
    }
}

• 3분만에 자신있게 완성했다. 그런데
  이게 뭐지?
• 제약사항에 문자열 s의 길이는 100,000이하의 자연수로 worst case가 크기는 한데,
  Stack의 push, pop, isEmpty는 O(1)이고, 전체 O(N)으로 해결한게 아닌가? 싶었다.
• 문제는 Stack연산에 없었고, 문자열의 split()에 있었다. 확인해보니 split()연산이 시간 복잡도가 O(N * M), 그러니까 이 문제 같은 경우 최대 O(N^2)이 나오는 것이다.
• 그러면 s를 어떻게 처리하지? 고민하다가 substring()연산으로 바꾸어 보았다. substring()은 O(N)의 시간복잡도로, for문 안에서 사용하면 어차피 O(N^2)이겠지만 그래도 한번 시도해 봤다.

import java.util.*;

class Solution {
    
    boolean solution(String s) {
        Stack<Integer> stack = new Stack<Integer>();
        
        for(int i=0; i<s.length(); i++){
            String brc = s.substring(i, i+1);
            if(brc.equals("(")){
                stack.push(1);
            }else if(brc.equals(")")){
                if(stack.isEmpty())
                    return false;
                stack.pop();
            }
        }
        
        if(stack.isEmpty())
            return true;
        else
            return false;
    }
}

쫌 되라

• 코딩테스트에서 제일 골치아픈 상황을 마주해버렸다.. 이문제는 사실 스택을 활용한 문제가 아니라 문자열 처리를 시간복잡도를 최소화하여 구현하는 문제였던 것이다.
• 아니, 그냥 내가 바보였던 것이다. String 클래스의 charAt()메서드를 사용하면 배열마냥 문자열의 특정 인덱스 값을 char형으로 가져올 수 있단다. 이런 세상에 자바 개발이 몇년짼데 이걸 몰랐다니..

👨‍💻 CODE

import java.util.*;

class Solution {
    
    boolean solution(String s) {
        Stack<Integer> stack = new Stack<Integer>();
        
        for(int i=0; i<s.length(); i++){
            char brc = s.charAt(i);
            if(brc == '('){
                stack.push(1);
            }else if(brc == ')'){
                if(stack.isEmpty())
                    return false;
                stack.pop();
            }
        }
        
        if(stack.isEmpty())
            return true;
        else
            return false;
    }
}