명함 지갑을 만드는 회사에서 지갑의 크기를 정하려고 합니다. 다양한 모양과 크기의 명함들을 모두 수납할 수 있으면서, 작아서 들고 다니기 편한 지갑을 만들어야 합니다. 이러한 요건을 만족하는 지갑을 만들기 위해 디자인팀은 모든 명함의 가로 길이와 세로 길이를 조사했습니다.
아래 표는 4가지 명함의 가로 길이와 세로 길이를 나타냅니다.
명함 번호 가로 길이 세로 길이 1 60 50 2 30 70 3 60 30 4 80 40 가장 긴 가로 길이와 세로 길이가 각각 80, 70이기 때문에 80(가로) x 70(세로) 크기의 지갑을 만들면 모든 명함들을 수납할 수 있습니다. 하지만 2번 명함을 가로로 눕혀 수납한다면 80(가로) x 50(세로) 크기의 지갑으로 모든 명함들을 수납할 수 있습니다. 이때의 지갑 크기는 4000(=80 x 50)입니다.
모든 명함의 가로 길이와 세로 길이를 나타내는 2차원 배열 sizes가 매개변수로 주어집니다. 모든 명함을 수납할 수 있는 가장 작은 지갑을 만들 때, 지갑의 크기를 return 하도록 solution 함수를 완성해주세요.
class Solution {
public int solution(int[][] sizes) {
int max = 0;
int min = 0;
for (int[] size : sizes) {
int paramMax = Math.max(size[0], size[1]);
int paramMin = Math.min(size[0], size[1]);
if (paramMax > max) {
max = paramMax;
}
if (paramMin > min) {
min = paramMin;
}
}
return max * min;
}
}
하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs가 매개변수로 주어질 때, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return 하도록 solution 함수를 작성해주세요. (단, 소수점 이하의 수는 버립니다)
import java.util.Arrays;
import java.util.PriorityQueue;
class Solution {
public int solution(int[][] jobs) {
// 총 시간은 대기시간(가변)+실행시간(불변)이므로, 대기시간이 짧을수록 짧아진다
// 대기시간(=시작시간-요청시간)을 짧게 하려면, 수행시간이 짧은걸 먼저 처리(SJF)
// 중요 개념 : 선점SJF 와 비슷
// 작업을 요청 시점 순으로 담고 있는 작업 큐
// 소요시간이 적은 순으로 작업을 수행하는 작업 큐
// 요청 시점에 가능한 작업들을 작업 큐에 넘겨주면, 소요시간이 적은 순서대로 우선순위를 부여하여 작업을 수행
int seconds = 0;
// jobs를 요청시간으로 정렬(asc)하는 prioirtyQueue 생성
PriorityQueue<Integer[]> jobQue = new PriorityQueue<>((o1, o2) -> o1[0].compareTo(o2[0]) );
// int[] -> Integer[] -> prioirtyQueue에 삽입
for (int[] job : jobs) {
jobQue.add(Arrays.stream(job).boxed().toArray(Integer[]::new));
}
// 계산
int size = jobQue.size();
int totalSeconds = 0;
while(!jobQue.isEmpty()){
if(seconds < jobQue.peek()[0]){
seconds++;
continue;
}
// 해당 시점에 실행할 수 있는 job관리 큐
PriorityQueue<Integer[]> availableQue = new PriorityQueue<>((o1,o2) -> o1[1].compareTo(o2[1]));
while(!jobQue.isEmpty() && jobQue.peek()[0] <= seconds){
availableQue.add(jobQue.poll());
}
// 대기시간(=시작시간-요청시간) + 실행시간
Integer[] currentJob = availableQue.poll();
totalSeconds += seconds - currentJob[0] + currentJob[1];
// 쓰지 않은 job은 모두 복구
jobQue.addAll(availableQue);
// 현재 작업 실행 완료 시점으로 jump!
seconds += currentJob[1];
}
return Math.round(totalSeconds/size);
}
}
풀이 방법
선점 SJF와 비슷 = 작업을 요청 시점 순으로 담아서 처리
잘못된 접근 : 작업시작 시간으로 정렬하는것에 집중한것이 실패의 요인
올바른 접근 : 당시의 최적의 해를 구하는 탐욕법과 비슷 => 매 시점마다 소요시간이 적게 걸리는 작업을 먼저 처리하는게 효율적이라는 풀이를 도출하는것이 중요하다
풀이
작업 요청 시간 별로 정렬-> 첫번째 실행 -> 완료 시점에서 실행가능한 작업중 완료시간이 가장 짧은 작업 실행 * n 번 실행
느낀점
그리디(탐욕법) : 당시의 최적의해를 찾는 방식을 계속하는 방식 -> 이 내용과 비슷
주요 로직 작업 요청 시간 별로 정렬-> 첫번째 실행 -> 완료 시점에서 실행가능한 작업중 완료시간이 가장 짧은 작업 실행 * n 번 실행
명령어 수신 탑(높이) I 숫자 큐에 주어진 숫자를 삽입합니다. D 1 큐에서 최댓값을 삭제합니다. D -1 큐에서 최솟값을 삭제합니다. 이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.
스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.
속한 노래가 많이 재생된 장르를 먼저 수록합니다. 장르 내에서 많이 재생된 노래를 먼저 수록합니다. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다. 노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.
트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.
예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.
일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다. 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다.
괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어
"()()" 또는 "(())()" 는 올바른 괄호입니다. ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다. '(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.
