[JS] 프로그래머스 주식가격

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

프로그래머스

 

 

 

목차

• 문제
• 풀이
• 코드

문제

입력

prices - 초 단위로 기록된 주식가격이 담긴 정수 배열

 

출력

return - 가격이 떨어지지 않은 기간 (몇 초, 정수)

 

제한사항

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

풀이

이 문제는 문제 자체를 이해하기 어려웠다. 주식 가격이 떨어지지 않다는 것이 무엇인지 파악하는 데에 시간이 걸렸다.

 

주어진 prices 배열을 순회할 때 타켓 원소를 v라고 한다면 v 보다 뒤에 있는 원소가 v보다 작은 원소를 만날 때까지 걸리는 시간을 구하는 것이다. 만나지 않는다면 시간은 끝까지 흐른다. 아직도 어렵다. 예시를 보자

 

[1, 2, 3, 5, 1]이라는 prices 배열이 주어졌다고 가정해보자.

 

prices 배열을 모두 순회하면서 타겟 원소가 타겟 원소보다 작은 원소를 만날 때까지 걸리는 시간을 새로운 배열에 입력하면 된다.

prices[0]은 나머지 모든 원소보다 작거나 같다. 따라서 배열 끝까지 가는 데 걸리는 시간인 4초가 걸린다.

prices[1]은 prices[4]를 만나기 전까지의 모든 원소가 작거나 같다. 그래서 총 3초가 걸린다. (prices[4]를 만나서 시간이 멈췄기 때문이다. 이 부분이 이해하기 쉽지 않다.)

prices[2]도 prices[4]를 만나기 전까지 조건을 만족하므로 2초가 걸린다.

prices[3]은 1초이고, prices[4]는 배열이 끝났으므로 0초이다.

 

따라서 반환해야 하는 배열은 [4, 3, 2, 1, 0]이다.

 

이를 코드로 나타내면 다음과 같은 과정을 따라야 한다.

1. prices의 모든 원소를 인덱스로 순회한다.
2. 타겟 원소의 인덱스보다 큰 인덱스로 나머지 원소들을 순회한다.
3. 나머지 원소들을 순회할 때 시간을 기록한다.
4. 나머지 원소 중 타겟 원소보다 작은 값을 만나면 내부 순회를 멈춘다.
5. 기록한 시간을 새로운 배열에 넣는다.

이렇게 적어도 감이 안온다. 코드를 보자. (이중 반복문이다. 순회가 두 번이다.)

 

시간 복잡도는 최악의 경우 prices의 배열의 길이를 n이라고 할 때 n-1+n-2+...+1이므로 O(n^2)이다.

공간 복잡도는 배열의 길이를 저장하므로 O(n)이다.

코드

function solution(prices) {
    var answer = [];
    
    for (let i=0; i<prices.length; i++) {
        let temp = 0;
        for (let j = i+1; j<prices.length; j++) {
            temp++;
            if (prices[i] > prices[j]) break;
        }
        answer.push(temp);
    }
    
    return answer;
}

 

이게 가장 깔끔한 풀이다. while문으로 바꿔도 상관 없다. 그러나 이중 반복을 할 때 인덱스를 활용하므로 for문을 활용하였다.

시간을 기록하는 변수의 이름을 좀 더 직관적인 것으로 바꾸면 좋았겠다. 어떤 이름이 좋을까.