스택/큐
1. 주식가격
문제 설명
트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.
예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.
// 입출력 예로 제시된 [1,2,3,2,3]을 보자
// 초 단위로 기록된 주식가격이 담긴 배열
// 1 : 끝까지 가격이 떨어지지 않음 4초
// 2 : 끝까지 가격이 떨어지지 않음 3초
// 3 : 1초동안 가격 x
// 2 : 끝까지 가격이 떨어지지 않음 1초
// 3 : 마지막 값이라 측정 x 0초
// 때문에 return 값은 [4,3,1,1,0]이 된다.
// 이중 for문해결
class Solution {
public 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;
}
}// 입출력 예로 제시된 [1,2,3,2,3]을 보자
// 초 단위로 기록된 주식가격이 담긴 배열
// 1 : 끝까지 가격이 떨어지지 않음 4초
// 2 : 끝까지 가격이 떨어지지 않음 3초
// 3 : 1초동안 가격 x
// 2 : 끝까지 가격이 떨어지지 않음 1초
// 3 : 마지막 값이라 측정 x 0초
// 때문에 return 값은 [4,3,1,1,0]이 된다.
import java.util.*;
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++){
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;
}
}2. 기능개발
문제 설명
프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.
또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.
먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.
// progresses라는 기능에서 speeds를 몇 일간 처리할 수 있는 지 출력하는 내용
class Solution {
public int[] solution(int[] progresses, int[] speeds) {
// 작업 개수 최소 100기준점 생성
int[] temp = new int[100];
// temp에 적용할 날짜 수
int day = 0;
// 각 항목마다 100까지 검사해야하므로 for(while)문
for(int i=0; i < progresses.length; i++){
while(progresses[i] + (speeds[i] * day) < 100){
day++;
}
temp[day]++;
}
int count = 0;
// temp에 0이 아닌값을 측정
// temp 배열 값을 하나씩 n에 적용하고 0이 아니라면 count 증가
for(int n : temp){
if(n != 0){
count ++;
}
}
int[] answer = new int[count];
// 초기화
count = 0;
// 다시 answer 배열에 값 넣기
for(int n : temp){
if(n !=0){
answer[count++] = n;
}
}
return answer;
}
}3. 다리를 지나는 트럭
문제 설명
트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.
예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.
import java.util.*;
// time : 총 걸리는 시간
// sum : 건너는 다리에 있는 truck의 총 무게
// 선입선출 방식 => Queue
class Solution {
public int solution(int bridge_length, int weight, int[] truck_weights) {
Queue<Integer> q = 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(q.isEmpty()){
q.add(truck);
time++;
sum+= truck;
break;
}
// 큐가 가득찬 경우
else if(q.size() == bridge_length){
// 먼저 들어간 차량 빼내기
sum -= q.poll();
}
// 큐가 가득차지 않은 경우
else {
if(sum + truck <= weight){
q.add(truck);
time++;
sum+= truck;
break;
} else {
q.add(0);
time++;
}
}
}
}
// 총 걸리는 시간과 다리길이 합 = 최소 걸리는 시간
return time + bridge_length;
}
}
Ethan Velog