2023.02.15(목) - 프로그래머스 고득점 Kit 스터디(스택/ 큐)
- 같은 숫자는 싫어
풀이 방법
- 배열을 한칸씩 이동하며 해당 index 의 수를 stack 에 삽입
- 삽입 하기 전에 stack 의 가장 위에 위치한 수와 일치 하는지 확인
. 이때 같지 않을때만 stack 에 삽입 한다.
- stack 이 비어 있다면 무조건 삽입
package suhyeongLee.Stack_Queue.No_Same_Num;
import java.util.Stack;
public class Solution {
public int[] solution(int []arr) {
Stack<Integer> stack = new Stack<>();
for(int i = 0; i < arr.length; i++){
if(stack.isEmpty()){
stack.push(arr[i]);
} else {
if(stack.peek() != arr[i]){
stack.push(arr[i]);
}
}
}
int[] answer = new int[stack.size()];
for(int i = answer.length-1; i >= 0; i--){
answer[i] = stack.pop();
}
return answer;
}
}- 기능개발
풀이 방법
- 작업은 첫번째 부터 배포 되어야 하기 때문에 첫번째 부터 확인
- day 를 하루씩 늘려 가며 해당 날짜에 완성도가 100이 넘게 되면 그 날짜에 배포 하는 기능을 +1 해 줌
. 이때 완성도는 "0일차의 완성도" + "하루 진행률 * day" 로 계산
- 넘지 않으면 day 를 늘려 진행도를 더 올림
package suhyeongLee.Stack_Queue.Funtion_dev;
import java.util.Arrays;
class Solution {
public int[] solution(int[] progresses, int[] speeds) {
int[] end_day = new int[100];
int day = -1;
for(int i=0; i<progresses.length; i++) {
while(progresses[i] + (day*speeds[i]) < 100) {
day += 1;
}
end_day[day] += 1;
}
return Arrays.stream(end_day).filter(i -> i!=0).toArray();
}
}
- 올바른 괄호
풀이 방법
- 올바른 괄호가 되기 위해서는 괄호가 열린 만큼 닫혀 줘야 함
- stack 을 이용해 '(' 가 나오면 삽입, ')' 가 나오면 '(' 를 제거 해 주는 방식으로 진행
- string 을 끝까지 순회 했을때만 stack 이 비어 있다면 올바른 괄호임
- String 의 가장 앞쪽부터 순서대로 가면서 다음 조건에 맞게 stack 에 삽입
. 현재 삽입할 char 가 '(' 일 경우에 stack 에 삽입
. '(' 가 아닐 경우에 pop 을 진행
- 위 작업 이 모두 끝나기 전에 stack 이 비게 되면 올바른 괄호가 아님
package suhyeongLee.Stack_Queue.Collect_parenthesis;
import java.util.Stack;
class Solution {
boolean solution(String s) {
boolean answer = true;
Stack<Character> stack = new Stack<>();
char[] str_arr = s.toCharArray();
for (int i = 0; i < str_arr.length; i++){
if(str_arr[i] == '('){
stack.push('(');
} else {
if(stack.isEmpty()){
answer = false;
break;
} else {
stack.pop();
}
}
}
if(!stack.isEmpty()){
answer = false;
}
return answer;
}
}- 프린터
풀이 방법
- 중요도를 우선 순위 큐에 넣어 출력할 프린트 물을 중요도 순으로 정렬(index 를 섞이게 됨)
- 이후 priority 배열을 순회 하면서
. queue 의 가장 위 숫자(가장 큰 우선순위)와 같은 우선순위를 가지는 프린트물을 탐색
. 발견시 pop 을 통해 큐에서 해당 우선 순위 제거
. 큐가 빌때 까지 반복
// 맨처음에는 가장 앞에서 부터 출력 하는줄 알았음
package suhyeongLee.Stack_Queue.Printer;
import java.util.Collections;
import java.util.PriorityQueue;
class Solution {
public int solution(int[] priorities, int location) {
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
int answer = 0;
for (int i = 0; i < priorities.length; i++) {
pq.add(priorities[i]);
}
while (!pq.isEmpty()) {
for (int i = 0; i < priorities.length; i++) {
if (priorities[i] == pq.peek()) {
if (i == location) {
answer++;
return answer;
}
pq.poll();
answer++;
}
}
}
return -1;
}
}
- 다리를 지나는 트럭
풀이 방법
- FIFO 인 큐를 통해 다리에 진입 한 트럭을 관리 하고 다리 위의 트럭수와 무게를 다리 길이와 제한 무게와 비교해 트럭을 더 진입 시킬지 진입 시키지 않고 기다릴지 결정함
- 트럭 배열을 처음부터 끝까지 돌며 다음 조건에 따라 queue 에 add, pop 한다.
. queue가 비었다면 다리가 빈 상태 이기 때문에 add 를 수행 한 후 무게를 더해준 다음 다음 트럭으로 넘어감
. queue의 size 가 다리의 길이와 같아진다면 다리가 꽉찼기 때문에 트럭을 한대 빼 준후 무게에서 해당 트럭의 무게를 빼줌
. 위 두 조건 모두 만족하지 않는다면 다리의 길이에 여유가 있기 때문에 무게를 비교하여 queue 에 add, pop 여부를 결정
package suhyeongLee.Stack_Queue.Truck;
import java.util.LinkedList;
import java.util.Queue;
class Solution {
public 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()) {
queue.add(truck);
sum += truck;
time++;
break;
} else if(queue.size() == bridge_length) {
sum -= queue.poll();
} else {
if(sum + truck <= weight) {
queue.add(truck);
sum += truck;
time++;
break;
} else {
queue.add(0);
time++;
}
}
}
}
return time + bridge_length;
}
}
- 주식가격
풀이 방법
- 주식 가격 배열을 처음부터 끝까지 돌면서 해당 시점의 가격이 다음날부터 언제 떨어지는지 stack 을 통해 확인
- stack 에는 index 를 관리하며 주식 가격 배열에 해당 시점의 가격보다 높거나 같은 날짜 수로 덮어 씀
package suhyeongLee.Stack_Queue.Price_of_Stock;
import java.util.Stack;
class Solution {
public int[] solution(int[] prices) {
int[] ans = 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()]) {
ans[stack.peek()] = i - stack.peek();
stack.pop();
}
stack.push(i);
}
while (!stack.isEmpty()) {
ans[stack.peek()] = prices.length - stack.peek() - 1;
stack.pop();
}
return ans;
}
}