[프로그래머스] 탑(java)

문제

탑

문제풀이

송전탑을 가로로 세운 후 오른쪽 탑부터 왼쪽으로 송신, 더 높은 탑만이 수신 가능한 문제이다.
1. 맨 오른쪽 탑으로 간다.
2. 한 칸씩 왼쪽으로 가면서 자신보다 큰 탑을 찾는다.
3. 찾았으면 맨 오른쪽 배열에 찾은 탑의 index 번호 삽입, 못찾았으면 0 삽입.
4. 맨 오른쪽 탑을 제외하고 1번부터 반복.

스택 s1, s2 두 개를 써서 pop과 push를 통해 문제를 풀었다. 하지만 내가 짠 코드는 스택을 너무 의식한 나머지 효율이 좋지 못하다. 왜냐하면 스택을 pop하면서 다음 탑을 찾고, 다시 그 스택에 넣어줘야 하기 때문이다. 차라리 배열같은 선형 자료구조를 통해 다음 탑을 찾는것이 훨씬 간편하고 빠를 것이다.

프로그램 코드

import java.util.*;
class Solution {
    public int[] solution(int[] heights) {
        int[] answer = new int[heights.length];
        Stack<Integer> s1 = new Stack<Integer>();
		Stack<Integer> s2 = new Stack<Integer>();
		
		int idx = 0;
		for (int i = 0; i < heights.length; i++) {// s1에 heights 요소push
			s1.push(heights[i]);
		}

		for (int i = heights.length; i > 1; i--) {
			int com1 = s1.pop();
			s2.push(com1); // s1에서 하나를 꺼내 s2에 push.

			while (!s1.isEmpty()) { // s1 끝까지 꺼내서 탐색
				idx++;
				int com2 = s1.pop();
				s2.push(com2);

				if (com1 < com2) { // 하나씩 꺼내서 비교
					answer[i - 1] = i - idx;
					while (idx != 0) {
						idx--;
						s1.push(s2.pop());
					}
					break;
				}
                if (s1.isEmpty()) { // 끝까지 찾았는데도 없다면
					while (idx != 0) {
						idx--;
						s1.push(s2.pop());
					}
					break;
				}
			}

		}
        return answer;
    }
}