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

📚 문제

명함 지갑을 만드는 회사에서 지갑의 크기를 정하려고 합니다. 다양한 모양과 크기의 명함들을 모두 수납할 수 있으면서, 작아서 들고 다니기 편한 지갑을 만들어야 합니다. 이러한 요건을 만족하는 지갑을 만들기 위해 디자인팀은 모든 명함의 가로 길이와 세로 길이를 조사했습니다.

아래 표는 4가지 명함의 가로 길이와 세로 길이를 나타냅니다.

가장 긴 가로 길이와 세로 길이가 각각 80, 70이기 때문에 80(가로) x 70(세로) 크기의 지갑을 만들면 모든 명함들을 수납할 수 있습니다. 하지만 2번 명함을 가로로 눕혀 수납한다면 80(가로) x 50(세로) 크기의 지갑으로 모든 명함들을 수납할 수 있습니다. 이때의 지갑 크기는 4000(=80 x 50)입니다.

모든 명함의 가로 길이와 세로 길이를 나타내는 2차원 배열 sizes가 매개변수로 주어집니다. 모든 명함을 수납할 수 있는 가장 작은 지갑을 만들 때, 지갑의 크기를 return 하도록 solution 함수를 완성해주세요.

제한사항

• sizes의 길이는 1 이상 10,000 이하입니다.
• sizes의 원소는 [w, h] 형식입니다.
• w는 명함의 가로 길이를 나타냅니다.
• h는 명함의 세로 길이를 나타냅니다.
• w와 h는 1 이상 1,000 이하인 자연수입니다.

📝 문제 해결

명함의 가로 세로를 바꿀 수 있으니 가로에는 배열의 큰 값, 세로에는 배열의 작은 값 중 가장 큰 값을 저장해준다.

💻 코드

public class No86491 {
    public static void main(String args[]){
        System.out.println(solution(new int[][]{{60, 50}, {30, 70}, {60, 30}, {80, 40}}));
        System.out.println(solution(new int[][]{{10, 7}, {12, 3}, {8, 15}, {14, 7}, {5, 15}}));
        System.out.println(solution(new int[][]{{14, 4}, {19, 6}, {6, 16}, {18, 7}, {7, 11}}));
    }
    
    public static int solution(int[][] sizes) {
        int w = 0, h = 0;
        for (int[] card : sizes) {
            w = Math.max(w, Math.max(card[0], card[1]));
            h = Math.max(h, Math.min(card[0], card[1]));
        }
        return w * h;
    }
}

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

📚 문제

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

제한사항

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

📝 문제 해결

이중 반복문을 통해 배열의 값을 하나씩 비교하며 가격이 떨어지지 않은 경우 answer을 1초씩 증가시키고, 만약 가격이 떨어질 경우 prices[i] > prices[j]  반복문을 빠져나온다.

💻 코드

public class No42584 {
    public static void main(String args[]){
    	System.out.println(solution(new int[]{1, 2, 3, 2, 3}));
    }
    
    public static 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++){
                answer[i]++;
                if (prices[i] > prices[j]) break;
            }
        }
        
        return answer;
    }
}

+) 스택을 이용한 풀이

가격과 위치(인덱스)를 배열에 저장하여 Stack에 넣어주고 Stack의 마지막으로 넣어준 가격과 현재 가격을 비교하여

현재 가격이 더 낮다면 Stack에서 값을 꺼낸 뒤, 현재 기간(i) - 해당 기간(Stack의 마지막)을 넣어준다. (현재 기간이 더 높을 때까지  반복)

[출처 : https://after-newmoon.tistory.com/40 ]

import java.util.*;

public class No42584 {
    public static void main(String args[]){
    	System.out.println(solution(new int[]{1, 2, 3, 2, 3}));
    }
    
    public static int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        Stack<Integer[]> stack = new Stack<>();
        
        for(int i = 0; i < prices.length; i++){
            answer[i] = answer.length - 1 - i;
            Integer[] arr = {i, prices[i]};
            
            while(!stack.empty() && stack.peek()[1] > prices[i]){
                Integer[] price = stack.pop();
                answer[price[0]] = i - price[0];
            }
            
            stack.push(arr);
        }
        
        return answer;
    }
}

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

📚 문제

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다. Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

📝 문제 해결

Priority Queue를 사용해서 숫자가 작을수록 우선순위를 가지게 저장해주고 큐에 2개 이상의 원소가 있을 때,

• 큐의 첫번째 값이 K보다 크면 answer을 return
• 아닐 때는 스코빌 지수가 제일 작은 두개를 꺼내 공식대로 섞어주고 다시 큐에 넣어주고 ➡️ answer 증가

큐의 사이즈가 1개가 되었을때, 모든 음식의 스코빌 지수가 K보다 커야하므로 큐의 첫번째 값이 K보다 작으면 -1을 return 해준다.

💻 코드

import java.util.PriorityQueue;

public class No42626 {
	public static void main(String[] args){
    	System.out.println(solution(new int[]{1,2,3,9,10,12}, 7));
    }
    
    public static int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> que = new  PriorityQueue<Integer>();
        for(int s : scoville) que.add(s);
        
        while(que.size() > 1){
            if(que.peek() >= K) return answer;
            int first = que.poll();
            int second = que.poll();
            que.add(first + (second * 2));
            answer ++;
        }
        
        if(que.peek() < K) return -1;
        return answer;
    }
}

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

📚 문제

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

경과 시간다리를 지난 트럭다리를 건너는 트럭대기 트럭

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

📝 문제 해결

다리에 트럭을 넣는 조건은 총 3가지가 있다.

1) 큐가 비어있는 경우 = 다리 위에 어떠한 트럭도 올라가지 않은 경우

2) 큐가 가득 차지 않은 경우

이미 다리에 있는 트럭의 무게와 다리에 올릴 다음 트럭의 무게를 비교해 다리에 올릴지 말지를 결정한다.

이미 다리에 있는 트럭의 무게와 다리에 올릴 다음 트럭의 무게다리의 무게를 넘게 되면 현재값 대신 0을 넣어준다.

3) 큐가 가득 찬 경우

트럭을 큐에서 꺼내 다리를 건너도록 해준다.

💡 마지막에 트럭이 다리에 올라가고 반복문을 탈출하기 때문에 마지막 트럭이 빠져나가는 시간을 다리의 길이를 더해줘야 한다.

💻 코드

import java.util.*;

public class No42583 {
	public staic void main(String args[]){
		System.out.println(soultion(2,10, new int[]{7,4,5,6}));
	}
    
	public static int solution(int bridge_length, int weight, int[] truck_weights) {
		Queue<Integer> queue = new LinkedList<>();
		int sum = 0;
		int time = 0; 

		for(int i = 0; i < truck_weights.length; i++) {
			int truck = truck_weights[i];

			while(true) {
				if(queue.isEmpty()){	// 1)
					queue.add(truck);
					sum += truck;
					time++;
					break;
				}else if(queue.size() == bridge_length){	// 3)
					sum -= queue.poll();
				}else{	// 2)
					if(sum + truck <= weight){
						queue.add(truck);
						sum += truck;
						time++;
						break;
					}else{ 
						queue.add(0);
						time++;
					}
				}
			}
		}

        return time + bridge_length; 
    }
}