lango

찍먹? 부먹?
난 부먹 개발자.

3 minute read




문제 풀이

이번 주식 가격 문제는 필자의 가독성이 부족한 것인지, 도저히 지문 자체가 이해가 안되어 지문을 이해하는 것이 더 어려웠다.
이 때, 다른 분의 지문 해석 글이 지문을 이해하는데 큰 도움이 되었기 때문에 해당 링크를 공유한다.

해당 글에서는 아래와 같이 지문을 이해하기 쉽게 알려주었다.


문제설명
n초 간의 주가를 초 단위로 기록한 배열 prices가 매개변수로 주어질 때, 각 초의 주가를 기준으로 해당 초 부터 n초 사이에 가격이 떨어지지 않은 시간은 몇 초인지 배열에 담아 return 하도록 solution 함수를 완성하세요.

제한사항
prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
prices의 길이 n은 2 이상 100,000 이하입니다. (2 <= n <= 100,000)

입출력 예 

1
2

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

입출력 예 설명

  • 1초의 주가는 1이며 1초부터 5초까지 총 4초간 주가를 유지했습니다.
  • 2초의 주가는 2이며 2초부터 5초까지 총 3초간 주가를 유지했습니다.
  • 3초의 주가는 3이며 4초의 주가는 2로 주가가 떨어졌지만 3초에서 4초가 되기 직전까지의 1초간 주가가 유지 된것으로 봅니다. 따라서 5초까지 총 1초간 주가를 유지했습니다.
  • 4초의 주가는 2이며 4초부터 5초까지 총 1초간 주가를 유지했습니다.
  • 5초의 주가는 3이며 5초 이후로는 데이터가 없으므로 총 0초간 주가를 유지했습니다.


문제에 활용할 자료구조

위에서 살펴본 지문을 통해 이해한 후에는 새로운 의문점이 생겼다. 바로 해당 문제의 유형이 스택/큐 문제로 지정되어 있었다는 것이다.
굳이 큐를 활용해서 peek한 원소와 나머지 원소를 비교해가며 할 수는 있겠지만 필자는 그냥 단순하게 배열을 활용하는 것이 좋을 것 같아 배열을 활용하여 풀었다.


아이디어 도출

지문을 잘 이해했다면 문제의 솔루션을 찾는 건 생각보다 쉽다.

  • 주어진 prices의 길이를 통해 1초부터 N초까지 각 원소의 정수값을 유지하고 있는지를 줌점으로 보면 된다.
  • prices의 원소를 순회하며 중첩 for문을 통해 해당 원소와 다음 원소와의 증감 여부를 비교하면 된다.
    • 이 때, 현재 원소가 다음 원소보다 작으면 주식 가격이 올라가는 중이기 때문에 또 다음 원소와 비교할 수 있도록 1초씩 증가시키고 다음 순회로 넘기면 된다.
    • 만약 현재 원소가 다음 원소보다 크다면, 즉 주식 가격이 하락했다면 하락되기 직전까지의 1초간은 주가가 유지된 것으로 보기 때문에 1초를 포함한 후 해당 순회를 멈춘다.
  • 위 과정을 반복하며 prices의 각 원소마다 중첩 for문을 통해 구한 주식가격 유지시간 값을 반환할 배열에 담으면 된다.


생각해낸 아이디어는 복잡할 수 있지만, 앞서 말했듯이 지문을 잘 이해했다면 간단할 수 있다.
그럼 바로 코드를 작성해보자.

1

int[] answer = new int[prices.length];

먼저 prices의 길이만큼 그대로 반환할 것이니 answer 배열을 prices의 길이와 동일하게 선언하자.

1
2
3
4
5
6
7
8
9
10
11
12

for(int i=0; i<prices.length; i++) {
    int term = 0;
    for(int j=i+1; j<prices.length; j++) {
        if(prices[i] <= prices[j]) term++;
        else if(prices[i] > prices[j]) {
            term++;
            break;
        }
        else break;
    }
    answer[i] = term;
}

주어진 prices를 통해 1초부터 [prices.length]초까지 가격이 떨어지지 않은 시간은 몇 초인지를 구하기 위한 로직은 다음과 같다.

  1. 중첩 for문을 통해 prices의 해당 원소와 다음 원소들을 순회하며 비교한다.
  2. 이 때, 각 원소마다 몇 초만큼인지를 구할 term 변수를 선언한다.
  3. 현재 원소(가격)가 다음 원소보다 작으면 주가가 상승하고 있다는 것이기에 term을 1 증가시키고 다음 원소를 순회하도록 한다.
  4. 만약, 현재 원소(가격)가 다음 원소보다 크다면 주가가 하락했다는 것이기에 term을 1 증가시킨 후, 현재 순회에서 멈추고 1초 뒤의 주가를 비교하도록 한다.
  5. 그 밖의 상황일 경우 쓸데없이 이중 for문을 순회할 필요가 없기 때문에 순회를 종료시킨다.

중첩 for문에서 j를 i+1부터 순회하도록 구현한 이유는 같은 원소끼리는 비교할 필요가 없기 때문이다.



작성 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {

        int[] answer = new int[prices.length];
        
        for(int i=0; i<prices.length; i++) {
            int term = 0;
            for(int j=i+1; j<prices.length; j++) {
                if(prices[i] <= prices[j]) term++;
                else if(prices[i] > prices[j]) {
                    term++;
                    break;
                }
                else break;
            }
            answer[i] = term;
        }
        return answer;
    }
    public static void main(String[] args){
        Solution sol = new Solution();
        int[] prices = new int[]{1,2,3,2,3};
        // int[] prices = new int[]{5,4,3,2,5};
        sol.solution(prices);
    }
}

회고

  • 중첩 for문 내에서 특정 조건에서는 순회를 이어가고, 특정 조건에서는 순회를 멈추도록 하는 로직을 통해 스택이나 큐를 활용하지 않고도 해당 문제를 풀 수 있었다.

You may also enjoy