[코테 준비 : day17] 스택/큐.2

1. 프로세스

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

[문제 풀이 고민]

• 우선 순위는 숫자가 큰것이 우선순위가 된다.
• 우선 순위에 따라 프로세스를 배치한 뒤, 해당 프로세스가 몇번째로 실행되는지 리턴

import java.util.*;

class Solution {
    public int solution(int[] priorities, int location) {
        int answer = 0;

        Queue<Integer> queue = new LinkedList<>();

        for (int i : priorities) {
            queue.add(i);
        }

        //array sorting 하기전에 먼저 Queue에 순서 그대로 집어넣기 때문에 괜찮음
        Arrays.sort(priorities);
        int size = priorities.length - 1;

        while (!queue.isEmpty()) {
            Integer i = queue.poll();
            //우선순위가 가장 높은지 확인
            if (i == priorities[size - answer]) {
                answer++;
                location--;
                if (location < 0)
                    break;
            } else {
                queue.add(i);
                location--;
                if (location < 0)
                    location = queue.size() - 1;
            }
        }
        return answer;
    }
}

---

2. 다리를 지나는 트럭

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

문제 풀이 고민 다리를 다 건너는데 몇초가 걸리는지를 리턴

• bridge_length는 1대의 차가 다리를 다 건너는 초가 된다
• weight는 다리에 올라갈 수 있는 차의 최대 무게

1. 처음 시작은 맨 처음 트럭을 넣고 초를 +1초 추가 해줌
2. 경우의 수를 나눈다.
   • 다리에 올라온 트럭의 수가 무게와 같을 경우 1개는 내린다.
   • 그외에 -> 1. 합이 클경우 뒤에 트럭을 넣지말고 0으로 대체
     2. 그외에는 큐에 넣고 합에 추가 후 +1초한다.

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;
        int sum = 0;
        Queue <Integer> queue = new LinkedList<>();

        for(int i = 0; i < truck_weights.length; i++){
            while(true){
                //처음 시작
                if(queue.isEmpty()){
                    queue.add(truck_weights[i]);
                    sum += truck_weights[i];
                    answer ++; //초 추가
                    break;
                }
                //다리에 모두 올라왔을 경우
                else if(queue.size() == bridge_length){
                    sum -= queue.poll();
                }
                else{
                    if(sum + truck_weights[i] > weight){
                        queue.add(0);//다음 트럭을 못데려오니 0으로 대체
                        answer++;
                    }
                    else{
                        queue.add(truck_weights[i]);
                        sum += truck_weights[i];
                        answer++;
                        break;
                    }
                }
            }
        }

        return answer + bridge_length;
    }
}

---

3. 주식가격(재 풀이 필요)

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

[문제 풀이 고민]

• 하나의 주식가격을 기준으로 이후 가격들이 떨어졌는지 아닌지 확인후 안 떨어진 초를 카운트해서 출력
  (예시) [1, 2, 3, 2, 3] 일 경우 1을 기준으로는 한번도 떨어진 적이 없기 때문에 4가 출력된다.

1. 몇몇 테스트 코드만 성공

• 시간복잡도에도 문제가 있음

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

        for(int i = 0; i < prices.length; i++){
            int prev = prices[i];
            int count = 0;
            for(int j = i + 1; j < prices.length; j++){
                if(prev <= prices[j]){
                    count ++;
                }
            }
            answer[i] = count;
        }

        return answer;
    }
}

• prices[stack.peek()] : 스택 맨 위에 있는 가격

(첫번째 반복문)

• 스택이 비어있지 않고,주식가격이 떨어졌을 때 answer에 값을 넣고 해당 인덱스는 stack에서 pop하는 로직 구현
• 그 외의 경우(스택이 비어있거나(=처음), 주식가격이 떨어지지 않았을 경우에는 해당 인덱스를 stack에 push

(두번째 반복문)
까지 stack에서 pop되지 않은 수가 있다. = 끝까지 가격이 떨어지지 않은 주식이 있다.
전체 길이에서 해당 인덱스를 빼주고, stack에서 pop하여 마무리

public class Solution {

    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < prices.length; i++) {
            while (!stack.isEmpty() && prices[i] < prices[stack.peek()]) {
                answer[stack.peek()] = i - stack.peek();
                stack.pop();  // 답을 구했기 때문에 stack에서 제거
            }
            stack.push(i);
        }

        while (!stack.isEmpty()) { // 값을 구하지 못한 index == 끝까지 가격이 떨어지지 않은 주식
            answer[stack.peek()] = prices.length - stack.peek() - 1;
            stack.pop();
        }

        return answer;
    }
}