프로그래머스) - 탑(Stack/Queue)

문제 출처입니다.

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

프로그래머스

 

스택/큐 영역에 있어서 스택으로 풀어야 할 것 같았지만 보자마자 배열이 생각나서 배열로 풀어보기로 했다.

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

뭐 이런식으로 작성을 했지만 계속 오류가 나서 다른사람들의 풀이를 보았다..ㅠㅠ

.

.

(↓수정본. 200402)

 

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

먼저 배열로 푼 사례

 

1. 배열

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

이 사례 역시 '각각의 탑을 배열로 설정하고 왼쪽으로 송신을 하기 때문에 가장 오른쪽에 있는 탑을 기준으로 왼쪽에 있는 탑과 비교한다'는 점에서 비슷하지만, 중간에 for문에서 j를 어떤 식으로 사용하였는지가 다르다. 여튼 스택을 이용한 풀이보다 훨씬 간단해서 보기 좋은 것 같다.

 

2. 스택

import java.util.*;
 
class Solution {
    class Tower {
        int idx;
        int height;
 
        public Tower(int idx, int height) {
            this.idx = idx;
            this.height = height;
        }
//탑에 대한 정보를 담는다
 
 
        @Override
        public String toString() {
            return "idx : " + idx + " height : " + height;
        }
    }
 
    public int[] solution(int[] heights) {
        Stack<Tower> st = new Stack<>();
        int[] answer = new int[heights.length];
 
        for (int i = 0; i < heights.length; i++) {
            Tower tower = new Tower(i + 1, heights[i]);
            int receiveIdx = 0;
 
            while (!st.isEmpty()) {
                Tower top = st.peek();
 
                if (top.height > tower.height) {
                    receiveIdx = top.idx;
                    break;
                }
 
                st.pop();
            }
 
            st.push(tower);
            answer[i] = receiveIdx;
        }
 
        return answer;
    }
}
 

이 풀이가 이 문제의 적합한 정답이라고 한다. 

 

 

느낀점: 그래도 저번보단 많이 늘은 것 같다. 하지만 너무 부족하다. 하루에 한 단원은 끝내야지.