Today's Algorithm(2018-10-22)

programmers 탑

수업시간에 다뤘던 문제인데.. 제가 문제를 풀고 있었던지 그 풀이가 기억이 안나네요. 그래서 아쉽지만 제가 풀었던 방법만 기록할 수 있을 것 같네요.

 

이 문제를 단순하게 정리하면 각 탑의 꼭대기에서 왼쪽 방향으로 전파를 보낼 때 걸리는 탑이 있으면 걸렸던 탑의 인덱스, 없으면 0을 배열에 넣으면 됩니다. 문제가 스택/큐 카테고리에 있는 만큼 최대한 스택/큐를 이용해보려 노력해봤는데요. 그래서 설계를 다음과 같이 하였습니다.

1. 왼쪽에서 하나씩 탐색 기준을 두면서 하나씩 기준을 증가시킨다.
2. 탐색 기준 이전까지 값들을 스택에 모두 넣어둔다.
3. 스택의 사이즈를 하나씩 줄이면서 탐색 기준 값보다 큰 값을 만나면 그 값의 인덱스(스택크기 + 1)를 배열에 저장하고 다음 탐색 기준으로 이동. 만약 스택 크기가 0이 될 때까지 큰 값이 없으면 0을 배열에 저장

소스 코드는 다음과 같습니다.

import java.util.Stack;

class Solution {
    public int[] solution(int[] heights) {
        int[] answer = new int[heights.length];
        Stack<Integer> tops = new Stack<>();

        for (int i = 0; i < heights.length; i++) {
            boolean pass = false;

            for (int j = 0; j < i; j++) {
                tops.add(heights[j]);  // 스택에 넣고
            }

            while(!tops.empty()) {
                if(tops.pop() > heights[i]) {
                    answer[i] = tops.size() + 1;  // 하나 pop()했으니 (남은 개수 + 1) 번째가 해당
                    pass = true;
                    break;
                }
            }

            if(!pass) {
                answer[i] = 0;
            }

            tops.clear();
        }
        return answer;
    }

}

while문 안에 if문 들어간 수를 구별하기 위해서 따로 flag를 써줬습니다. 왜냐하면 Stack의 크기가 0이더라도 인덱스 0이 제일 높은 탑일 때가 포함되기 때문입니다. 그리고 주의해줘야 할 점이 있는데 변수 i가 도는 for문에서 마지막에 tops를 비워두어서 다음 스택에 값을 넣을 때 영향을 주지 않도록 하여야 한다는 것입니다.