[Algorithm/java] 주식가격

Jay·2020년 12월 29일
0

Algorithm

목록 보기
17/44
post-thumbnail

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

제한사항

prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
prices의 길이는 2 이상 100,000 이하입니다.

입출력 예

prices [1, 2, 3, 2, 3]
return [4, 3, 1, 1, 0]

입출력 예 설명

1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.


접근하기

  • 자신으로부터 뒤의 숫자들 중 언제 자신보다 큰 숫자가 나오는지 판별
  • 순서대로 쌓되 FIFO가 되어야 함으로 큐를 사용.
  1. 모든 배열을 큐에 집어 넣고
  2. 큐에서 맨 앞 하나씩 빼면서 해당 숫자보다 큰 다음 숫자 위치를 판별
  3. 자신보다 큰 숫자가 없을 경우를 처리하기 위해 boolean flag이용.

Code

import java.util.*;
class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        
        Queue<Integer> q = new LinkedList<>();
        
        //1.모든 배열을 큐에 집어넣음.
        for(int i=0; i<prices.length; i++){
            q.offer(prices[i]);
        }
        
        //2. 큐에서 맨 앞 하나를 빼면서 해당 숫자보다 큰 다음 숫자의 위치를 찾음.   
        boolean flag = true;
        int count = 0 ;
        while(!q.isEmpty()){
            int firstPrice = q.poll();
            int startIdx = prices.length - q.size();            
            for(int a = startIdx; a < prices.length; a++){
                if(firstPrice > prices[a]){                    
                    answer[count] = (a-startIdx+1);
                    flag = false;
                    break;
                }
            }
            
            //가격이 떨어진 시점이 없다면
            if(flag){
                answer[count] = q.size();
            }
            
            flag=true;
            count++;
        }
        
        return answer;
    }
}
  • 나름 코드의 핵심이라 말한다면 flag를 고를 것이다. 가격이 떨어지지 않는다고 가정하고 true로 시작하며 떨어지는게 발견된 시점에 false로 고쳐주고 그 시점을 answer에 넣는다.

다른 사람의 풀이

class Solution {
    public int[] solution(int[] prices) {
        int len = prices.length;
        int[] answer = new int[len];
        int i, j;
        for (i = 0; i < len; i++) {
            for (j = i + 1; j < len; j++) {
                answer[i]++;
                if (prices[i] > prices[j])
                    break;
            }
        }
        return answer;
    }
}
  • 제..일 깔끔한 코드.. 분기 처리를 하는게 더러워보여서 이런걸 지향해야할 듯..
profile
Android Developer - Come to my medium (https://medium.com/@wodbs135)

0개의 댓글