[프로그래머스/JS] Lv2 - 주식가격 # Array # Stack

 

https://school.programmers.co.kr/learn/courses/30/lessons/42584

프로그래머스

 

TIL

- 배열 초기화 할 때 Array(길이) 만 했는데, 추후에 이 배열에 데이터를 넣을 것이라면 Array(길이).fill(0) 이렇게 초기화 해주는게
  더 빠르다

 

문제 접근 방식

어떻게 이전에 올랐던 가격을 추적할 수 있을까..

가장 간단한 방법은 1초마다 가격이 변동될 때마다 이전에 형성된 모든 가격들의 정보와 비교하는 것입니다. 이 경우 N*N으로 느릴 것 같다는 생각이 들었습니다. 이미 하락했음에도 이너 포문 때문에 불필요한 가격 비교 로직이 들 것입니다.

 

나보다 크거나 작은 이전/이후의 첫 번째 요소를 찾는 문제는 스택을 활용하면 좋다고 합니다. 

 

문제 핵심 뽀인트
현재 시점의 가격(현재가)보다 나중에 가격이 떨어지는 시점을 찾아라!

 

 

스택에는 { 주가, 주가 형성됬던 time } 두 개의 타입이 담기게 됩니다.시간의 흐름에 따라서 현재 가격이 변할 때마다, 이전에 스택에 저장된 과거 가격들을 비교하는데, TOP을 기준으로 현재가보다 낮다면 하락한 것이기 때문에 현재 시점 time - 이전 주가 형성 시점 time 을 빼면 상승했던 time(second)가 나옵니다 나옵니다.

 

top은 과거에 형성된 가격 정보입니다.

 

"주식 가격이 1, 2, 3, 4, 5로 오르다가 누군가 대량의 매도 물량을 던져 현재가가 2가 되었다고 가정해봐야 합니다". 이 급격한 하락은 스택에 쌓여 있던 이전에는 차곡 차곡 상승했던 3, 4, 5 세 가격보다 낮아지는 가격이 됩니다.

이처럼 연속적인 하락이 발생할 경우를 대비해야 합니다. 따라서 스택의 맨 위 가격이 현재가보다 '더 이상 낮지 않을 때까지' (즉, 가격이 떨어지지 않을 때까지) 지속적으로(while문) 스택을 검사하고 정답을 확정하는 로직이 필요한 것입니다."

 

1. 스택에는 현재 가격을 담는데, 과거에 형성된 가격보다 높을 경우만 저장한다.
2. 현재가보다 스택에 저장된 가격이 낮을 경우에 지금 현재가격의 시간 - 그 가격이 형성된 시간 차이만큼을 정답 배열에 저장한다.
3. 그리고 pop으로 방출한다. 그럼 또 2번의 경우처럼 이전에 형성된 가격이 있는데 현재 가격이랑 비교해서 내려간 가격이라면, 2번을 실행. 3번 반복..
4. 마지막으로 스택에 저장된 내용들을 전부 빼면서 남아있는 시간을 정답 배열에 기록합니다.

 

const solution = (price) => {
    let answer = Array(price.length).fill(0)
    let tracked = price.reduce( (tracked, cur, idx) => {
        while (tracked.length > 0 && tracked.at(-1)[0] > cur) {
            let popped = tracked.at(-1)
            answer[popped[1]] = idx - popped[1]
            tracked.pop()
        }
        tracked.push([cur,idx])
        return tracked
    }, [])
    tracked.forEach(e => { answer[e[1]] = price.length-1 - e[1] })
    return answer
}

 

Array 파해치기

 

at(-1)은 마지막 인덱스 반환 Array.at()로도 요소 찾을 수있음

Array.from()
Array.of()
// 모두 새로운 배열 요소를 생성함. 
//   이때 of는 요소 하나 하나를 나열해서 넣어도 됨
//   from은  iterable한 Set, Map, String같은거를 Array로 변환할 때 사용됨

Array.push(... elements)
Array.pop() // 배열 끝 요소 하나 제거하고 반환함
Array.shift() // 배열 시작 요소 하나 제거하고 반환 Queue의 Dequeue
Array.unshift(...elements) // swift의 insert느낌,, 배열의 시작 index에 데이터 넣을 수 있음

Array.splice(start, deleteCount, ...items) // 특정 위치에 요소 조작
	// e.g. const fruits = ['apple', 'bana', 'cher', date']
    //      const removed = fruits.splice(1, 2)
    //      console.log(fruits) // ['apple', 'date']
    // 		console.log(removed) // 삭제된거 두 개 ['bana', cher']

    //      const fruits = ['apple', 'bana', 'cher', date']
    //      const removed = fruits.splice(1,1, 'grape', 'lemon') 
    //      console.log(fruits) // [애플, 그래이프, 레몬, cher, date]
    //      console.log(updated)  // ['bana']

Array.splice(startIndex, endIndex) 
    // 배열의 지정된 startIndex -> end Index직전까지의 요소 복사해서 새로운 배열로 반환함
    // e.g. const numbers = [1,2,3,4,5]
    //      const partial = numbers.slice(1,3) // 2, 3까지 복사
    
    
Array.fill(value, start, end) 
// 이때 end 인덱스 전까지만 fill
// 만약 end가 배열 길이 초과한다면? 마지막 인덱스까지 채워짐

Array.reverse()
Array.concat(value1, value2 ...)

	// e.g. const arr1 = [1,2] ; const arr2 = [3,4];
    //      const accumulatedArray = arr1.concat(arr2) // 새로운 배열 반환
    // 근데 이거 대신 스프레드 ... 이거 더 많이 쓴다고함
    
    //      cosnt accumulatedArray = [...arr1, ...arr2] // [1,2,3,4]
    
Array.join(separator) // 구분자 연결해서 문자로 만듬
Array.includes(value, fromIndex) // from부터 시작하고자 할 원소 찾음 기본 index = 0. bool값 반환

 

 

Array.indexOf(value, startIndex) // startIndex부터 value와 일치하는 첫번째 index찾음 startIndex 디폴트 값 0
Array.lastIndexOf(value, start) // start는 가장마지막 index. 맨 오른쪽부터 역순으로 value와 일치하는 첫 index 찾음

Array.toReversed() // 뒤집힌 배열  반환
Array.toSorted(compareFn) // 소팅된 배열 반환
Array.toSpliced(start, deleteCount, ...items) 요소를 삭제, 추가, 교체한 새로운 배열 반환함
Array.with(index, value) // 원본 변경x. index의 요소를 새로운 value로 교체한 "새로운 배열"을 반환한다고 한다.

 

고차함수들

Array.forEach(callback) // 루프
Array.map(callback) // 푸르 돌며 새 요소 반환
Array.filter(callback) 
Array.reduce(callback, initialvalue)
Array.reduceRight(callback, initialValue) // 옹 오른쪽에서 왼쪽으로 순차적으로 돌면서 reduce
Array.find(callback) // 조건 만족하는 첫 요소 값 반환. 없으면 undefined
Array.findIndex(callback)
Array.findLast(callback) // 조건 만족하는 마지막 요소 값 반환. 없으면 undefined
Array.findLastIndex(callback)
Array.same(callback) // 요소 중 하나라도 조건 만족시 true else false
Array.every(callback) // 모든 요소가 조건 만족해야 true반환
Array.flat(callback) 중첩배열 평탄화 Swift.compactMap


Array.keys() 
// 배열의 모든 값을 순회하는 iterator 객체 반환 
// 이제,, 숫자로만 이루어진 경우엔 index반환함 (그런데 key-value 같은 Map 형식에선 key 반환함)

Array.values() 배열을 iterator 객체로 반환
Array.entries() 배열의 [인덱스,값] 쌍 순회하는 Array Iterator 반환
// 역시나 Map Iterator처럼 Array Iterator는 Array.from 같은 함수를 통해서 Array로 바꿔야만 고차함수
// 쓸 수 있다.

 

References

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/Array

Array() 생성자 - JavaScript | MDN