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++ 풀이
'Algorithm > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 완주하지 못한 선수 (0) | 2020.05.17 |
---|---|
[프로그래머스] 다리를 지나는 트럭 (0) | 2020.05.16 |
[2019 카카오] 무지의 먹방 라이브 (0) | 2020.04.12 |
[2019 카카오] 후보키 (0) | 2020.04.11 |
[2020카카오공채] 블록 이동하기 (0) | 2020.04.04 |