[프로그래머스] 스택/큐 - 주식 가격

🙄💰 주식가격

😀문제

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

제한사항

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

입출력 예

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

입출력 예 설명

• 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
• 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
• 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
• 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
• 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

※ 공지 - 2019년 2월 28일 지문이 리뉴얼되었습니다.

---

이 문제는 배열 인덱스 간의 거리를 구하는 문제이다. 처음부터 이렇게 다가갔으면 좋았겠지만 나는 숫자로 밖에 보이지않았다. 다음부터는 거리라는 개념을 머리속에 넣고 문제를 만나야 겠다.

🥕 나의 풀이

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];

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

        return answer;
    }
}

처음에 한 개의 값을 잡고 그 다음값부터 끝까지 비교를 해서 커지면 ++ 해주고 작아지면 거기서 멈추는 식으로 구현했다. 두번째에 있는 else if 문에는 문제에 있는 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다. 에서 다음 index가 작더라도 1초는 내려가지 않았다. 라고 판단했기 때문에 저렇게 주었고, 마지막 index에는 무조건 0이 들어가기 때문에

1. 가격을 비교했을때 다음 값이 더 작고
2. 마지막 index가 아니라면
3. 1초동안 가격이 내려가지 않았다고 판단하고 +1초를 해준다.

라는 생각으로 넣어주었다.

---

🥕 다른사람의 풀이

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];

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

이 풀이를 보고 아차! 하는 생각이 들었다. 문제를 보고 바로 거리를 계산한다는 생각을 하지 못한 내 실수이다. 시간복잡도는 똑같지만, 이 방법으로 푸는게 조금 더 효율적이라고 생각이 든다.