[leetCode/JS] 901. Online Stock Span

문제 설명

Design an algorithm that collects daily price quotes for some stock and returns the span of that stock's price for the current day.

The span of the stock's price in one day is the maximum number of consecutive days (starting from that day and going backward) for which the stock price was less than or equal to the price of that day.

For example, if the prices of the stock in the last four days is [7,2,1,2] and the price of the stock today is 2, then the span of today is 4 because starting from today, the price of the stock was less than or equal 2 for 4 consecutive days.
Also, if the prices of the stock in the last four days is [7,34,1,2] and the price of the stock today is 8, then the span of today is 3 because starting from today, the price of the stock was less than or equal 8 for 3 consecutive days.
Implement the StockSpanner class:

StockSpanner() Initializes the object of the class.
int next(int price) Returns the span of the stock's price given that today's price is price.

 

입출력 예

Example 1:

Input : ["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
        [[], [100], [80], [60], [70], [60], [75], [85]]
Output : [null, 1, 1, 1, 2, 1, 4, 6]

Explanation
StockSpanner stockSpanner = new StockSpanner();
stockSpanner.next(100); // return 1
stockSpanner.next(80); // return 1
stockSpanner.next(60); // return 1
stockSpanner.next(70); // return 2
stockSpanner.next(60); // return 1
stockSpanner.next(75); // return 4, because the last 4 prices (including today's price of 75) were less than or equal to today's price.
stockSpanner.next(85); // return 6

Constraints

1 <= price <= 10^5
At most 104 calls will be made to next.

---

내 솔루션

• stock들이 나보다 낮을 동안 count를 올려 리턴한다.

class StockSpanner {
    constructor() {
        this.stocks = []
    }
    next(price) {
        this.stocks.unshift(price)
        let count = 0
        for(let i = 0; i < this.stocks.length; i ++){
            if(this.stocks[i] <= price){
                count++;
            } else {
                break;
            }
        }
        return count;
    }
};

최고의 솔루션

• 가격이랑 count를 남겨서 배열의 요소의 숫자를 줄이는 발상이 좋았다.
• 최적화 기술과 아이디어가 정말 대단한 듯.

var StockSpanner = function(prices) {
  this.prices = [];
};
StockSpanner.prototype.next = function(price) {
    let c = 1;
    while (this.prices.length>0 && price>=this.prices[this.prices.length-1][0]) { //go left in our condensed array
      c += this.prices[this.prices.length-1][1]; //add the grouped counts of smaller elements
      this.prices.pop(); // get rid of < values now that we've got their count, elim unnecessary data
    }
  this.prices.push([price, c]) //add grouped element to our condensed array
  console.log(this.prices)
  return c; //return last count for # days <= current
}

const stockSpanner = new StockSpanner();
stockSpanner.next(100); // [[100, 1]]
stockSpanner.next(80);  // [[100, 1], [80, 1]]
stockSpanner.next(60);  // [[100, 1], [80, 1], [60, 1]]
stockSpanner.next(70);  // [[100, 1], [80, 1], [70, 2]]
stockSpanner.next(60);  // [[100, 1], [80, 1], [70, 2], [60, 1]]
stockSpanner.next(75);  // [[100, 1], [80, 1], [75, 4]]
stockSpanner.next(85);  // [[100, 1], [85, 6]]

---

감상평

• leetcode는 질문 자체가 가볍고 이해하고 푸는 것 자체는 쉽지만
  찐개발자들이 만드는 최적화 방법은 정말 감탄스럽다. 개똑똑이 무우우친.