Today's Algorithm(2018-10-15)

programmers 쇠막대기

이 문제는 수업시간에 다루었던 내용입니다. Stack 자료구조를 사용하면 쉬운 문제인데요. 우선 코드부터 보겠습니다.

import java.util.Stack;

class Solution {
    public int solution(String arrangement) {
        int answer = 0;
        Stack<String> arrageStack = new Stack<>();
        String[] arragements = arrangement.split("");
        for(int i = 0; i < arragements.length; i++) {
            if(arragements[i].equals("(")) {
                arrageStack.push(arragements[i]);
                answer++;
            }
            if(arragements[i].equals(")")) {
                if(arragements[i-1].equals("(")) {
                    answer--;
                    arrageStack.pop();
                    answer = answer + arrageStack.size();
                } else {
                    arrageStack.pop();
                }
            }

        }
        return answer;
    }
}

스택 자료형 1개와 배열을 사용하여 문제를 풀었는데요. 다음과 같은 의문이 들수 있습니다.

왜 굳이 스택을 사용해야 하나? ArrayList 나 다른 자료구조 이용해도 remove(), add()를 이용하면 스택이 가진 기능 다 쓸 수 있지 않나?

맞는 말입니다. 하지만 스택이라는 패러다임을 가지고 보면 문제를 더 쉽게 풀 수 있습니다. 이게 큰 차이는 아닌 것 같지만 생각 하나만 바꾸어도 훨씬 더 쉽게 접근할 수도 있습니다. 또 pop()이나 push() 메서드를 쓰면 인덱스를 쓸 필요도 없구요.

 

제가 문제를 풀면서 쇠막대기 개수의 규칙은 아래와 같습니다.

1) (가 나오면 쇠막대기 개수 +1 시킨다

2) () 발사가 되면 그 이전의 (의 개수만큼 증가시킨다. 하지만 발사 모양 중 )가 나오기 전에 (에서 +1 되었으므로 -1 시키고 (또 빼줘야 하므로 pop()을 한다

3) )나올 때는 조용히 스택에 있는 (을 pop()한다

 

이런 규칙을 가지고 풀었는데 처음엔 답이 안나왔습니다. 괄호 배열을 쓰지않고 스택만 썼었는데요. 그러다보니 push(), pop()하면서 인덱스가 변동되면서 특히 14줄에서 제대로 비교가 안되었기 때문입니다. 그래서 배열을 함께 씀으로써 해결하였습니다. 자료구조에서 빼고 넣고 하면서 인덱스 변동이 있는 경우 이에 유의하면서 인덱스 계산을 해야할 것 같습니다.

 

다른 사람들의 풀이를 보니 보통 split("")으로 분할할 필요없이 charAt()을 통해 char형으로 비교를 대부분 하네요. 굳이 배열이 필요가 없었네요... 증가하는 부분의 위치 차이는 있지만 (와 )의 경우로 나누고 )의 경우 그 앞의 (조건 비교를 하는 틀은 다 비슷한 것 같아요!