stack/queue

프로그래머스 주식가격

완전탐색 풀이

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        int idx=0;

        for(;idx<prices.length;idx++){
            int sec=0;
            for(int i=idx+1;i<prices.length;i++){
                ++sec;
                if(prices[idx]>prices[i]){
                    break;
                }
            }

            answer[idx]=sec;
        }

        return answer;
    }
}

• 가장 처음에 떠올렸던 방향이다. 나에게 그나마 가장 익숙한 배열적인 사고방식이다.
  주가 하나에 대해서 뒤의 주가들을 탐색하며 가격이 하락했는지 판단한다.

그런데 이 문제가 스택/큐인 이유가 있다.
다음은 스택으로 풀어본 방법이다.

스택 풀이

• 나에게 스택의 사용을 고려할 상황을 생각해보면-> 최근에 담은 순대로 pop해가며 검사할 필요가 있을 때 정도 밖에 생각나지 않았다.

그런데 이 문제를 풀면서 느낀 것은

--- 그나마 익숙한 탐색방식- 한 요소에 대해 배열의 다른요소들을 돌며 검사 하는 것과 다르게
요소들의 집합들과 배열을 한 요소를 비교해가며 집합의 수정하는 방식으로도 접근할 수 있음을 유념해야겠다.
이 문제에서는 값이 하락하지 않은 주가들 스택을 구성하고 , 배열을 돌며 하락하면 pop하는 방식으로 효율성을 개선할 수 있다.

---stack은 특정 조건을 검사해가며 push(),pop() 함으로써 스택의 최상단 값에 특성을 부여할 수 있다는 것도 기억을 해놔야겠다.
이 특성을 이용하면 배열처럼 모든 값을 검사하지 않아도 되어 효율성이 향상될 수 있다.

import java.util.Stack;

class Solution {
    public int[] solution(int[] prices) {
        int[] ans=new int[prices.length];
        //아직 값이 떨어지지 않은 주가들 저장할 스택
        Stack<Integer[]> stk=new Stack<>();
        Integer[] tmp={prices[0],0};
        stk.push(tmp);
        
        int i=1;
        for(;i<prices.length;i++){
            //스택의 최대주가에 비해 가격 떨어짐
            while(!stk.isEmpty() && stk.peek()[0]>prices[i]){
                int idx=stk.peek()[1];
                ans[idx]=i-idx;
                stk.pop();
            }
            
            Integer[] tmp2={prices[i],i};
            stk.push(tmp2);
        }
        
        while(!stk.isEmpty()){
            ans[stk.peek()[1]]=i-1-stk.peek()[1];
            stk.pop();
        }
        return ans;

    }
}

아래의 방법은 stack에 인덱스를 담음으로써 위처럼 약식의 key,value지료구조(int[]) 를 쓰지 않아도 되는 방법이다.

class Solution {
    public int[] solution(int[] prices) {
        Stack<Integer> beginIdxs = new Stack<>();
        int i=0;
        int[] terms = new int[prices.length];

        beginIdxs.push(i);
        for (i=1; i<prices.length; i++) {
            while (!beginIdxs.empty() && prices[i] < prices[beginIdxs.peek()]) {
                int beginIdx = beginIdxs.pop();
                terms[beginIdx] = i - beginIdx;
            }
            beginIdxs.push(i);
        }
        while (!beginIdxs.empty()) {
            int beginIdx = beginIdxs.pop();
            terms[beginIdx] = i - beginIdx - 1;
        }

        return terms;
    }
}

다리를 지나는 트럭

차가 지나가는 것을 queue의 선입선출과 연결지었다면 풀 수 있었다.

시간이 지남에 다라 queue에 트럭을 add하고 poll하면서 트럭이 지나가는 것을 구현한다.
다리의 길이제한, 다리의 무게제한을 고려해서 트럭을 올리고 제한 때문에 트럭을 올릴수 없다면 add(0) 한다. while의 사이클마다 시간측정(++time)을하며 트럭을 지나가게 한다(q.poll()).

import java.util.Queue;
import java.util.LinkedList;


class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int time = 0;
        int[] w=truck_weights;
        int in_w=0;
        int truck_idx=0;
        //bridge length길이의 큐, 합해서 weight이하라면 큐에 넣음.
        //1초에 1 lenght만큼 전진.
        
        Queue<Integer> q= new LinkedList<>();
        q.add(w[truck_idx]);
        ++time;
        in_w+=w[truck_idx];
        ++truck_idx;
        int polled=0;
        
        while(!q.isEmpty()){
            
            if(q.size()>=bridge_length){                
                in_w-=q.peek();
                //마지막 트럭이 지나감
                if(truck_idx==w.length && q.peek()==w[truck_idx-1] && polled==w.length-1 ){
                    ++time;
                    break;
                }
                if(q.peek()!=0){++polled;}
                q.poll();
                
            }
            
            if( (truck_idx<w.length) && (in_w+w[truck_idx]<=weight) ){
                q.add(w[truck_idx]);
                in_w+=w[truck_idx];
                ++truck_idx;
            }   
            else{
                q.add(0);
            }
            
            ++time;
        }
        
        return time;
    }
}