[프로그래머스/javascript] 주식 간격 풀이 (문제 해설 포함, 자바스크립트, js)

[프로그래머스/자바스크립트] 주식 간격 풀이

( 문제 해설 포함, JavaScript , js )

프로그래머스 자바스크립트 주식 간격 풀이 ( JavaScript, js)

 

 

 

1. 문제

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

프로그래머스

 

 

 

---

2. 문제 이해 (문제 해설)

1. 문제 지문 재해석 풀이 

https://school.programmers.co.kr/questions/20326?question=20326

 

2. 지문 해설

https://school.programmers.co.kr/questions/24131

 

이 문제의 핵심은, n초 시점에 그다음 숫자가 있다면, '1초' 흐른 것이기 때문에 '1초'로 치는 것이다

[프로그래머스/자바스크립트] 주식 간격 풀이 ( JavaScript , js )

사진으로 예시를 보면 위와 같다.

 

1의 경우는 1-2초, 2-3초, 3-2초, 2-3초까지 총 4초가 흘렀기 때문에 4다.

2의 경우는 2-3초, 3-2초, 2-3초 까지 총 3초가 흘렀기 때문에 3이다.

3의 경우는 3-2초까지 총 1초가 흘렀기 때문에 1이다. (일단 떨어지지 않은 기간은 1초가 있기 때문에)

2의 경우는 2-3초까지 총 1초가 흘렀기 때문에 1이다.

3의 경우는 3초 다음 주식 가격이 없기 때문에, 그냥 0이다.

---

3. 코드

3-1. 첫 번째 코드 (모두 시간초과로 실패)

function solution(prices) {
    var answer = [];

    for (let i = 0; i< prices.length; i++) {
        let array = prices.slice(i, prices.length);
        let count = 0;

        for (let j = 1; j < array.length; j++) {
            // 만약 array 길이가 2인데 다음 값이 있다면 
            count++;
            
            if (array[j] <  prices[i] ){ 
                break;
            } 
        }
        
        answer.push(count);    
        
    }

    return answer;
}

- 정확성은 모두 통과지만, 효율성에서 모두 실패가 나왔다. 

일단 로직 자체는, prices 배열에서 0초 가격부터 n초까지 반복해서 잘라서 새로운 배열을 만들고,

현재 기준이 되는 초 (prices[i])보다 뒤에 시점의 array[j]의 주식 가격이 작아질때 클때까지 count를 증가시킨다.

 

만약에 기준이되는 초보다 더 큰 시간이 나온다면 해당 초를 정답에 추가한다.

2중 반복문에 slice로 반복할때마다 배열를 자르기 때문에 문제가 생긴 것 같다. 

 

 

 

3-2. 두 번째 코드 (효율성 1개만 성공, 나머지는 모두 시간초과)

function solution(prices) {
    var answer = [];

    while (prices.length > 0) {
        let nowSec = prices.shift();
        
        let array = prices;
        // console.log(array);
        let count = 0;

        for (let j = 0 ; j < array.length; j++) {
            count++;
            // 가격이 "떨어지지 않는 기간"을 계산한다. (가격이 떨어지면 바로 정지 = 가격이 떨어지는 순간)
            if (array[j] <  nowSec ){ 
                break;
            } 
        }
        
        answer.push(count);    
        
    }

    return answer;
}

- 일단 기존의 슬라이스 해서 배열을 모두 자르는 걸 없애고, 현재 기준이 되는 시간을 shift함수로 꺼내줬다.

- 이렇게 조금 줄였긴 했는데,,,, 그래도 슬라이싱 하는 것만 줄어든 거라 해결되지는 않았다.

 

---

3-3. 세 번째 코드 (성공)

function solution(prices) {
    var answer = []; //new Array(prices.length).fill(0);

    for (let i = 0; i< prices.length; i++) {
        let count = 0;

        for (let j = i+1; j < prices.length; j++) {
            // 만약 array 길이가 2인데 다음 값이 있다면 
            count++;
            
            if (prices[j] <  prices[i] ){ 
                break;
            } 
        }
        
        answer.push(count);    
        
    }

    return answer;
}

 

그냥 처음 값을 모두 꺼내는 것을 없애고, 

두 번째 반복문 (for)에서 j의 시작 지점을 기준이 되는 가격 시간대로 되도록 옮겼다.

이렇게 하면 nowSec (기준 지점)을 따로 shift 하거나 슬라이스 하지 않아도 가능하다. 

결국 두 번째 for문의 반복 횟수를 줄였다.

 

 

---

 

4. 마무리

 

결과적으로 해결하긴 했다.

하지만 이렇게 해도 결국에는 2중 for문이고 prices의 길이가 10000이 아니라 더 커지면 문제가 발생할 것 같다. 

첫 번째 루프의 시간복잡도는 O(n)이고, 그 안에서 두 번째 반복문이 최대 n-i-1번 실행이 되기 때문에,

결국에는 전체 반복 횟수가 O(n^2)가 된다.

 

스택/큐 계열 문제인 만큼 다음번에는 자료구조를 이용해서 풀어야 할 것 같다.

 

문제 이해가 어려웠고 이상한 부분에서 헷갈려서 결국은 1시간 30분 넘게 풀이와 해석을 보고 해결했다.

그래도 나름 풀어서 다행이다!

---

 

읽어주셔서 감사합니다~

도움이 되셨다면 공감 부탁드립니다 😊

틀린 부분 피드백은 언제나 환영입니다 🔥