코딩테스트 고득점 kit / 스택/큐 / 탑 / JAVA

 

 

풀이 방법1

import java.util.Stack;

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

        for(int height : heights) {
            stack.push(height);
        }

        while(!stack.isEmpty()) {

            int height = stack.pop();

            for(int i=stack.size(); i>=0; i--) {
                if(height < heights[i] ) {
                    answer[stack.size()] = i+1;
                    break;
                }
            }
        }
        return answer;
    }   
}

 문제의 취지대로 스택으로 접근한 방법입니다.

스택을 사용한다고 해서 peek와 pop을 비교해주는 방법으로 생각한다면 조금 어려워집니다.

이 풀이의 핵심은 스택에 탑 높이를 순차적으로 넣은다음

하나씩 차례대로 pop을 해서 해당 값을 heights배열의 이전 값과 비교하는 것입니다.

 

 

 

풀이 방법2

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

주식가격 문제와 유사하길래 한번 배열로 접근해봤습니다.

이중 for문을 이용하여 다음 순서와 값을 비교하면서 채워넣는 방법입니다. 

 

 

 

수행 속도 비교

	풀이 방법 1	풀이 방법 2
1차 수행 속도	45,700	1,100
2차 수행 속도	43,600	1,300
3차 수행 속도	46,200	1,300
평균 수행 속도	약 45,167	약 1,233

 

 

 

히스토리

chucoding/algorithm