[프로그래머스 / 스택/큐 / 자바(JAVA)] 주식가격

 

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42584

 

[ 요약 ]

시작 시간 : AM 8:53

종료 시간 : AM 9:33

소요 시간(분) : 40분

 

도전 횟수 (제출 횟수) : 3

로직 및 풀이 참고 여부 : X

 

[ 풀어보기 ]

정답 풀이

📌 로직

사실,, 스택 / 큐 문제인데 스택 / 큐 로 안 풀었다 큼큼.. 이중 for문으로 풀었다.

스택 / 큐 풀이 보고 배워가야겠다.

1. 비교대상을 순회할 for문 1개 (int i=0; i<prices.length-1; i++)
   • 마지막 요소는 비교할 대상이 없으므로, i는 prices.length-1 미만까지만 증가한다.
2. 그리고 그 안에, prices[i] 와 비교할 요소를 순회할 for문 1개 (int j=i+1; j<prices.length; j++)
3. 만약 prices[i] 보다 prices[j] 가 더 크거나 같으면, 가격이 그 때까지 떨어지지 않았다는 것이므로 answer[i]++;
4. 그렇지 않은 경우 j for문을 벗어난다.

 

📌 코드

import java.util.*;

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

 

📌 채점 결과

정확성  테스트
테스트 1 〉	통과 (0.03ms, 80.6MB)
테스트 2 〉	통과 (0.02ms, 76.2MB)
테스트 3 〉	통과 (0.23ms, 77.8MB)
테스트 4 〉	통과 (0.16ms, 74MB)
테스트 5 〉	통과 (0.28ms, 70.6MB)
테스트 6 〉	통과 (0.02ms, 79.4MB)
테스트 7 〉	통과 (0.13ms, 76.6MB)
테스트 8 〉	통과 (0.13ms, 73.7MB)
테스트 9 〉	통과 (0.02ms, 74.8MB)
테스트 10 〉	통과 (0.19ms, 74.9MB)

효율성  테스트
테스트 1 〉	통과 (20.97ms, 71.9MB)
테스트 2 〉	통과 (15.38ms, 68.6MB)
테스트 3 〉	통과 (14.68ms, 70.1MB)
테스트 4 〉	통과 (17.18ms, 70MB)
테스트 5 〉	통과 (11.60ms, 62.3MB)

채점 결과
정확성: 66.7
효율성: 33.3
합계: 100.0 / 100.0

 

---

 

오답 풀이 

📌 로직

나름 스택 / 큐로 열심히 풀어보려 했음을 ㅠ_ㅠ

1. 여기서도 이중 for문을 쓰긴 한다. 
   
   • 비교대상 순회 i for문과, prices[i] 와 비교할 요소를 순회하는 j for문을 이용하는 것은 같음.
2. 만약 prices[i] 보다 prices[j]가 더 크면, stack에 prices[j]를 push하고, 더 작은 prices[j] 가 나온 경우 break; 한다.
3. answer[i] 는 stack의 size() 가 된다.
4. stack의 내용물을 지워준다.

 

📌 코드

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        Stack<Integer> s = new Stack<>();
        
        for(int i=0; i<prices.length-1; i++) {
            for(int j=i+1; j<prices.length; j++) {
                if(prices[i]<=prices[j]) s.push(prices[j]);
                else break;
            }
            answer[i] = s.size();
            s.clear();
        }
        
        return answer;
    }
}

 

📌 채점 결과

1초 간이라도 유지된 경우가 0으로 처리되었다... ㅠㅠ

 

 

그래서 for문의 조건식이나, if문의 조건식을 이것저것 바꾸어봤으나, 해결되진 않았다.

answer[i] = s.size()==0?1:s.size(); 같은 시도도 해봤는데..

일단 코드를 쓰면서도 너무 억지 같기도 했고, 테스트 케이스는 통과하지만 채점은 통과 되지 않았다ㅠ_ㅠ 

 

정확성  테스트
테스트 1 〉	통과 (0.27ms, 76MB)
테스트 2 〉	실패 (0.32ms, 77.7MB)
테스트 3 〉	실패 (1.55ms, 84.9MB)
테스트 4 〉	실패 (1.06ms, 66.5MB)
테스트 5 〉	실패 (2.01ms, 76.3MB)
테스트 6 〉	실패 (0.27ms, 71.2MB)
테스트 7 〉	실패 (1.33ms, 81.5MB)
테스트 8 〉	실패 (0.79ms, 72.9MB)
테스트 9 〉	실패 (0.29ms, 74.8MB)
테스트 10 〉	실패 (1.68ms, 85.2MB)

효율성  테스트
테스트 1 〉	실패 (104.88ms, 77.2MB)
테스트 2 〉	실패 (78.23ms, 76.3MB)
테스트 3 〉	실패 (105.59ms, 77.8MB)
테스트 4 〉	실패 (93.30ms, 76.7MB)
테스트 5 〉	실패 (시간 초과)

채점 결과
정확성: 6.7
효율성: 0.0
합계: 6.7 / 100.0

---

[ 좋은 풀이 ]

 

손석현 님, Leenamgyo 님, 최지훈 님, 박태준 님 외 11 명

📌 코드

import java.util.Stack;

class Solution {
    public int[] solution(int[] prices) {
        Stack<Integer> beginIdxs = new Stack<>();
        int i=0;
        int[] terms = new int[prices.length];

        beginIdxs.push(i);
        for (i=1; i<prices.length; i++) {
            while (!beginIdxs.empty() && prices[i] < prices[beginIdxs.peek()]) {
                int beginIdx = beginIdxs.pop();
                terms[beginIdx] = i - beginIdx;
            }
            beginIdxs.push(i);
        }
        while (!beginIdxs.empty()) {
            int beginIdx = beginIdxs.pop();
            terms[beginIdx] = i - beginIdx - 1;
        }

        return terms;
    }
}

 

돌아가는건 알겠는데 어떤 과정을 거쳐서 도출해낸건지 잘 모르겠다 ...

 

prices를 순회하면서,

• prices[i] 보다 크거나 같은 값의 인덱스는 stack에 남겨둔다.
• prices[i] 보다 작은 값의 인덱스는 stack에서 제거하고, 인덱스간의 차를 통해 시간을 계산한다.

 

순회 후에 stack에 남은 인덱스들 = 끝까지 값이 떨어지지 않았음을 의미.

마지막 인덱스와, stack의 인덱스간의 차를 구해 시간을 계산한다.