2020년 11월 22일 일요일

[Algorithm] 스택&큐 ( 주식가격 )


문제 ]

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때,

가격이 떨어지지 않은 기간은 몇 초인지를 return하시오.


- 입출력 예

prices : [ 1, 2, 3, 2, 3]

return : [ 4, 3, 1, 1, 0]




제출 ]

선택정렬 비스무리한 느낌이나서 이중 for문으로 해결하면 되지 않을까?

하는 생각으로 stack을 사용하지 않고 제출


class Solution {

    public int[] solution(int[] prices) {

        int len = prices.length;

        int[] answer = new int[len];


        for(int i=0; i<len; i++){

            for(int j=i+1; j<len; j++){

                answer[i]++;

                if (prices[i] > prices[j]){

                    break;

                }

            }

        }

        return answer;

    }

}



제출 2 ]

Stack을 이용한 다른분의 풀이


import java.util.Stack;

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;

    }

}


- Int형 제네릭 스택 선언, 스택함수로는

stack.push(obj) : 가장 탑에 데이터 추가

stack.pop() : 최근에 추가된 데이터 삭제

stack.peek() : 최근에 추가된 데이터 조회

stack.empty() : stack값이 비었는지 확인, 비면 True 아니면 False


 

댓글 없음:

댓글 쓰기