[240601] 코딩 테스트 문제 풀기

🔶코딩테스트

---

≣ 목차

/ 오늘의 TIL /

---

코딩테스트

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

정답

ArrayDeque<Integer> stack = new ArrayDeque<>();

int len = prices.length;
int[] answers = new int[len];

//stack 초기값 설정
stack.push(0);

for (int i = 1; i < len; i++) {
    //스택을 사용해 이전 가격과 현재 가격 비교
    while (!stack.isEmpty() && prices[stack.peek()] > prices[i]) {
        //주식 가격이 떨어진 경우
        int idx = stack.pop();
        answers[idx] = i - idx;
    }
    stack.push(i);
}

//주식 가격이 떨어지지 않은 경우
while (!stack.isEmpty()) {
    int idx = stack.pop();
    answers[idx] = len - 1 - idx;
}
return answers;

숏코딩

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

시간 초과

채점 결과

정확성: 66.7

효율성: 13.3

합계: 80.0 / 100.0

import java.util.*;

public class Solution {
    /**
     *
     * @param prices 주식 가격이 담긴 원본 배열
     * @return 가격이 떨어지지 않은 기간(초)
     */
    public static int[] solution(int[] prices) {

        ArrayDeque<Integer> stack = new ArrayDeque<>();
        Map<Integer, Integer> map = new HashMap<>();

        int len = prices.length;

        for (int i = 0; i < len; i++) {
            map.put(i, prices[i]);
        }

        A: for (int i = 0; i < len-1; i++) {
            for (int j = i+1; j < len; j++) {

                //주식 가격이 떨어지지 않은 경우
                if (map.get(i) <= map.get(j)) {
                    stack.push(i);
                }
                //주식 가격이 떨어진 경우는 1번만 추가
                else {
                    stack.push(i);
                    continue A;
                }
            }
        }

        int[] answer = new int[len];
        //스택이 비어있을 때까지 데이터 추가
        while (!stack.isEmpty()) {
            answer[stack.pop()]++;
        }
        return answer;
    }


    public static void main(String[] args) {
        int[] a = {1, 2, 3, 2, 3};
        solution(a);
    }
}