[Programmers] 탑 - 스택/큐

10213 단어 algorithmalgorithm
import java.util.Stack;

// 탑 - 스택/큐
public class Top {

	public int[] solution(int[] heights) {

		Stack<Integer> stack = new Stack<Integer>();
		boolean flag; // 스택에 push 하는 값이 있는지 없는지 판별하는 플래그 선언

		for (int i = heights.length - 1; i >= 1; i--) {
			flag = false;
			for (int j = i - 1; j >= 0; j--) {

				if (heights[i] < heights[j]) { // 자신보다 높은 탑이 왼쪽에 있을 때
					stack.push(j + 1);
					flag = true; // 스택에 push 하는 값이 있을 때 flag를 true로 지정
					break;
				}
			}
			if (!flag) { // 스택에 push하는 값이 없을 때 (flag 가 false 일때), 즉 수신하는 탑이 없을 때 스택에 0을 push
				stack.push(0);
			}
		}
		stack.push(0); // 맨 왼쪽 탑의 신호를 수신하는 탑이 없으므로 스택에 0을 push

		int[] answer = new int[heights.length];
		for (int i = 0; i < answer.length; i++) {
			answer[i] = stack.pop();
		}
		return answer;

	}

	public static void main(String[] args) {

		Top s = new Top();

		int[] arr1 = { 6, 9, 5, 7, 4 }; // 0,0,2,2,4
		int[] arr2 = { 3, 9, 9, 3, 5, 7, 2 }; // 0,0,0,3,3,3,6
		int[] arr3 = { 1, 5, 3, 6, 7, 6, 5 }; // 0,0,2,0,0,5,6

		s.solution(arr1);
		s.solution(arr2);
		s.solution(arr3);

	}

}

좋은 웹페이지 즐겨찾기