Table of contents

프로그래머스 탑

수평 직선의 탑 N대의 높이 heights가 주어졌을 때, 각 탑이 송신한 레이저를 수신한 탑을 구하는 문제이다. 각 탑이 송신한 레이저는 해당 탑보다 왼쪽에 있는 탑 중에서 더 높은 높이를 가진 탑 중 첫번째 탑이 수신한다.

풀이

일반 반복문으로 푸는게 훨씬 편하지만, 스택/큐에 분류되어있는 문제라서 두 개의 스택을 이용해서 풀어봤다.

@Test
public void test() {
    assertThat(solution(new int[]{6, 9, 5, 7, 4}))
        .isEqualTo(new int[]{0, 0, 2, 2, 4});

    assertThat(solution(new int[]{3, 9, 9, 3, 5, 7, 2}))
        .isEqualTo(new int[]{0, 0, 0, 3, 3, 3, 6});

    assertThat(solution(new int[]{1, 5, 3, 6, 7, 6, 5}))
        .isEqualTo(new int[]{0, 0, 2, 0, 0, 5, 6});
}

private int[] solution(int[] heights) {
    Stack<Integer> stack = new Stack<>();
    Stack<Integer> stack2 = new Stack<>();
    int[] result = new int[heights.length];
    for (int i = 0; i < heights.length; i++) {
        stack.push(i);
    }

    for (int i = 0; i < heights.length; i++) {
        while (!stack.isEmpty() && stack.peek() >= i) {
            stack2.add(stack.pop());
        }

        while(!stack.isEmpty()) {
            int j = stack.pop();
            stack2.push(j);
            if (heights[j] > heights[i]) {
                result[i] = j + 1;
                break;
            }
        }

        while (!stack2.isEmpty()) {
            stack.push((stack2.pop()));
        }
    }

    return result;
}

각 탑이 송신한 레이저는 해당 탑의 왼쪽으로 송신된다.

while (!stack.isEmpty() && stack.peek() >= i) {
    stack2.add(stack.pop());
}

첫 번째 스택에서 해당 인덱스의 탑을 꺼낼 때까지 노드를 꺼내고 다시 두 번째 스택에 저장한다. 두 번째 스택에 저장하는 이유는 추후에 첫 번째 스택을 원상복구하기 위함이다.

while(!stack.isEmpty()) {
    int j = stack.pop();
    stack2.push(j);
    if (heights[j] > heights[i]) {
        result[i] = j + 1;
        break;
    }
}

첫 번째 스택에서 해당 인덱스의 탑이 가진 높이보다 더 높은 높이를 가진 탑을 찾을 때까지 노드를 꺼내고 다시 두 번째 스택에 저장한다. 더 높은 높이를 가진 탑을 만나면 결과를 갱신하고 중지한다.

while (!stack2.isEmpty()) {
    stack.push((stack2.pop()));
}

두 번째 스택에서 모든 노드를 꺼내서 다시 첫 번째 스택에 저장한다. 이를 수행함으로써 첫 번째 스택에 다시 (0, 1, 2, 3,4 5)와 같은 최초 상태가 저장된다.

두번째 풀이

단순 반복문을 사용해서 해결할 수도 있다.

@Test
public void test2() {
    assertThat(solution2(new int[]{6, 9, 5, 7, 4}))
        .isEqualTo(new int[]{0, 0, 2, 2, 4});

    assertThat(solution2(new int[]{3, 9, 9, 3, 5, 7, 2}))
        .isEqualTo(new int[]{0, 0, 0, 3, 3, 3, 6});

    assertThat(solution2(new int[]{1, 5, 3, 6, 7, 6, 5}))
        .isEqualTo(new int[]{0, 0, 2, 0, 0, 5, 6});
}

public int[] solution2(int[] heights) {
    int[] result = new int[heights.length];

    for (int i = 0; i < heights.length; i++){
        for (int j = i + 1; j < heights.length; j++){
            if (heights[i] > heights[j]){
                result[j] = i + 1;
            }
        }
    }


    return result;
}

이번에는 레이저를 송신하는 탑을 기준으로 탐색하지 않고, 수신하는 탑을 기준으로 탐색한다.