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

문제 및 코드

 

회고

• 일단 가장 먼저 들었던 생각은 아래와 같다. 이중 for문 쓰면 시간초과 날 것 같아서 스택이나 큐로 풀려고 했다. 근데 이중 for문 써도 시간초과 안 나네..? 배신감을 느낌
• 큐로 해야하는지 스택으로 해야 하는지 갈피가 안 잡혀서 엄청 고민하다가 큐로 했는데 테케 1만 통과하고 다 틀림... 그래서 결국 다른 풀이를 봤음
• 스택으로 잘 풀어져있는 코드가 있었음. 나는 계속 주식 가격을 집어 넣고 빼고, 가격이 오른 거를 계속 유지하려고 하고 그랬는데 발상의 전환으로 가격 자체가 아니라 가격의 인덱스를 집어 넣고 빼고, 가격이 떨어진 거만 먼저 구한 다음 나중에 가격이 계속 유지되었던 것만 구하는 방식으로 풀이가 구현되어 있었음. 어떻게 이런 생각을 하지? 

// prices를 n중 for문으로 돌면서 일일 확인해도 될 것 같긴한데 길이가 100000으로 길어서 초과될듯...

// 큐를 만든다
// 정답 배열을 만든다
// prices를 돈다
    // 큐가 비어 있으면
        // 가격을 큐에 넣는다
    // 큐가 비어있지 않으면 큐에 들어있는 값의 수만큼 for 돌기(이때의 큐 사이즈를 미리 기억해서 딱 그 횟수만 돌도록 해야 함)
        // 현재 가격과 큐에서 뽑은 가격 중 현재 가격이 더 크거나 같다
            // 작은 for문 인덱스를 바탕으로 정답 배열 값 1 증가, 큐에서 값 빼서 뒤로 넣기
        // 현재 가격과 큐에서 뽑은 가격 중 현재 가격이 더 작다
            // 큐에서 값 빼서 뒤로 넣기
        
        // for문 다 돌고 난 이후 현재 가격 큐에 넣기, 

        
import java.util.*;


class Solution {
    public int[] solution(int[] prices) {
        Queue q = new LinkedList();
        
        // 정답 배열
        int[] answer = new int[prices.length];
        
        // prices 돌기
        for(int i = 0; i
            int curr = prices[i];
            
            if(q.isEmpty()){
                q.add(curr);    
            }else{
                int size = q.size();
                for(int j = 0; j
                    int target = q.peek();
                    if(curr >= target){
                        answer[j] += 1;
                        int value = q.poll();
                        q.add(value);
                    }else{
                        int value = q.poll();
                        q.add(value);
                    }
                }
                q.add(curr);
            }
        }
        
        return answer;
    }
}

체크

풀이 횟수	시간	정답 여부	참고 여부
1	2시간		O