[프로그래머스] 탑

https://programmers.co.kr/learn/courses/30/lessons/42588

코딩테스트 연습 - 탑

import java.util.Stack;

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

        for (int i = heights.length - 1; i >= 0; i--) {
            while (!st.isEmpty() && heights[i] > heights[st.peek()]) {
                answer[st.pop()] = i + 1;
            }
            st.push(i);
        }

        return answer;
    }
}

 

스택을 이용해 풀면 O(n)에 푸는것이 가능하다(사실 이 문제는 2중 for문으로도 풀리는듯)

 

자바에서 스택은 pop을 할 때 top이 return된다. 짱 좋음!

 

#include <string>
#include <vector>
#include <stack>

using namespace std;

vector<int> solution(vector<int> heights) {
	vector<int> answer(heights.size(), 0);
	stack<int> st;

	for (int i = heights.size() - 1; i >= 0; i--) {
		while (!st.empty() && heights[i] > heights[st.top()]) {
			answer[st.top()] = i + 1;
			st.pop();
		}
		st.push(i);
	}

	return answer;
}

 

C++ 풀이