알고리즘 풀이 - 프로그래머스(쇠막대기, 스택)

 

이번 문제는 복수의 쇠막대기를 절단 시 잘려서 남은 쇠막대기의 개수를 구하는 문제이다.

 

문제 설명

 

여러 쇠막대기를 수직으로 겹쳐 놓고 레이저를 발사해 자르는데 아래와 같은 조건을 만족해야 한다.

 

조건

 - 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓인다.
 - 쇠막대기를 다른 쇠막대기 위에 놓을 시, 완전히 포함되도록 놓되 끝점은 겹치지 않는다.
 - 각 쇠막대기를 자르는 레이저는 적어도 하나 이상 존재한다.
 - 레이저는 어떤 쇠막대기의 양 끝점에 겹치지 않는다.

 

예시

쇠막대기와 레이저 배치 예시 - 점선은 레이저로 쇠막대기를 자르는 레이저

 

위 그림의 예시에서 셀 수 있듯이 결과는 17개가 나온다.

(a) 레이저는 여는 괄호와 닫는 괄호의 인접 쌍으로 표현 : "()"
(b) 쇠막대기의 왼쪽 끝은 여는 괄호 "(" 이고, 오른쪽 끝은 닫힌 괄호 ")" 이다.

 

 

해결 방안1 - Stack 활용

 

현재 쇠막대기의 개수가 몇 개인지와 그 상태에서 레이저가 맞는지 여부를 판별하여 잘려서 결과로 나온 쇠막대기의 전체 개수를 구하는 방식으로 문제를 풀었다. 다음의 코드를 보자.

import java.util.Stack;
class Solution {
    public int solution(String arrangement){
        int answer = 0;
        int stick = 0;
        Stack<Character> stack = new Stack<>();
        for(int i=0; i < arrangement.length(); i++){
            char curr = arrangement.charAt(i);   
            if(curr == ')'){
                if(stack.peek() == '('){
                    stick -= 1;
                    answer -= 1;
                    answer += stick;
                } else {
                    stick--;
                }
            } else {
                stick++;
                answer++;
            }
            stack.push(curr);
        }
        return answer;
    }
}

 

이 코드의 테스트 결과는 다음과 같다.

 

 

해결 방법2 - 배열만 이용

public int solution(String arrangement){
    char[] arr = arrangement.toCharArray();
    int answer = 0;
    int stick = 0;
    for(int i=0; i < arr.length; i++){
        if(arr[i] == ')'){
            if(arr[i-1] == '('){
                stick -= 1;
                answer -= 1;
                answer += stick;
            } else {
                stick -= 1;
            }
        } else {
            stick += 1;
            answer += 1;
        }
    }
    return answer;
}

 

이 문제도 사실 위와 같이 배열만 이용해서 풀 수 있다. 이 문제는 규칙이 있다.

1) 여는 괄호와 닫는 괄호가 연속으로 오는 경우 - 레이저로 판단
2) 닫는 괄호와 닫는 괄호가 연속으로 오는 경우 - 쇠막대기의 끝으로 판단

즉, 현재 값이 여는 괄호 '(' 라면 그냥 무조건 쇠막대기의 수를 더해주는 것이다. 그리고 만약 다음에 닫는 괄호가 왔다면 쇠막대기가 아니라 레이저 였던 것이므로 다시 쇠막대기의 값을 내려주고 레이저로 쇠막대기를 자른 만큼 더해주면 된다.

닫는 괄호만 연속이라면 단순히 쇠막대기 수를 줄여주면 된다. 이 코드에 따른 테스트 결과는 다음과 같다.

 

 

결과를 보면 2번 방법이 더 빨랐음을 알 수 있다. 사실상 코드가 거의 동일함에도 불구하고 배열이 더 빠른 것은 Stack을 선언함에 있어서의 차이가 아닐까 예상은 해본다. 그러나 확실하지는 않다. 이 부분에 대해서는 추가적인 공부가 많이 필요할 듯 하다.