Java / Programmers /올바른 괄호

https://school.programmers.co.kr/learn/courses/30/lessons/12909?language=java

프로그래머스

 

1. ArrayList를 통한 접근 방법

class Solution {
    boolean solution(String s) {
        boolean answer = true;
        ArrayList<Character> stack = new ArrayList<>(); //1
        
        for (int i=0; i < s.length(); i++) {
            char curr = s.charAt(i);
            stack.add(0, curr);
            if (i==0 & curr==')') { //2
                return false;
            }
            
            if (stack.size() > 1) { //3
                if (stack.get(0)==')' &
                    stack.get(1)=='(') {
                    stack.remove(0);
                    stack.remove(0);
                }

            }
        }
        if (stack.size() > 0) { //4
            return false;
        }
        return answer;
    }
}

로직이 나온 이유

1. Array에는 크기의 변화가 안된다. 따라서 크기가 변할때마다 배열을 새로 복사해야 하는데 이는 메모리상 매우 안 좋아보였다.(사실 이는 확인해봐야한다. ArrayList의 생성 방식을 정확히 몰라서 확답할 순 없다.) 그래서 크기의 변화가 있어도 되는 ArrayList를 선택했다.
2. 리스트에 더해질때 리스트가 비어있는 상태고 ')'가 들어오면 False를 반환했다.(여기서 골때렸던건 ' "의 차이였다. '=char, "=str이다.)
3. ArrayList의 사이즈가 1보다 크면 삭제할게 있는지 확인한다.(ArrayList는 [i]로 조회할 수 없다. get()을 써야한다.)
4. for문이 전부 돌아갔을 때 ArrayList에 잔여물이 있으면 False를 리턴한다.

 

쓰읍.... 왜 효율성에서 터지는지 모르겠다.

for문을 전부 돌아서 터지는건 아닌거 같다. 그 이유는 아래 정답 코드 수행시간과 비교하면 전체적으로 약 6배의 차이가 난다.(애시당초 처음부터 조건을 걸어놔서 전부 돌았을리도 없다)

개인적으로는 get, remove에 내 눈에는 보이지는 않지만 데이터 소모가 있지 않았나 싶다.

 

 

2. 일종의 stack

class Solution {
    boolean solution(String s) {
        boolean answer = true;
        int stack = 0;
        for (int i=0; i < s.length(); i++) {
            char curr = s.charAt(i);
            if (curr == '(') {
                stack +=1;
            } else if (curr==')') {
                stack-=1;
            }
            if (stack < 0) {
                return false;
            }
        }
        if (stack != 0) {
            return false;
        }
        return answer;
    }
}

로직이 나온 이유

1. 어떻게 리펙토링을 할까 하다가 그러면 그냥 지우고, 더하는 과정을 없애기로 했다. 따라서 숫자를 세는 방법을 고안했다.
2. 덕분에 ArrayList를 만드는 과정도 제거가 되었다.