프로그래머스 탑(heights) 정답 코드

난이도 ★★☆☆☆

 

문제를 보시려면 여기를 클릭

 

 

 

힌트

주식가격 문제와 완전히 동일한 로직으로 Queue를 쓰지 않고 구현했습니다. 왜 필요한지 잘 모르겠네요...?;; 코드 짧게 빠르게 풀긴 했는데 O(n^2)이라 찝찝합니다. 더 좋은 로직 아시는 분은 공유 부탁드립니다.

 

 

 

이하는 코드입니다.

public class Solution {
    public int[] solution(int[] heights) {
        int[] answer = new int[heights.length];
        answer[0] = 0; // always 0
 
        // O(n^2)
        for (int i = heights.length - 1; i > 0; i--) {
            int answerPos = 0;
 
            for (int j = i - 1; j >= 0; j--) {
                if (heights[j] > heights[i]) {
                    answerPos = j + 1;
                    break;
                }
            }
 
            answer[i] = answerPos;
        }
 
        return answer;
    }
}