프로그래머스 큐 문제
💡 기능 개발
- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42586
- 문제 요약 : 현재 진행률(progresses)와 일간 작업속도(speeds)가 주어졌다. 개발은 동시에 시작하고 누가 끝나는 지는 순서와 상관이 없다. 다만, 앞선 개발이 완료된 시점에야 다음 개발을 배포할 수 있다. 만약 앞선 개발을 배포할 때 다음 개발도 완료됐다면 동시에 배포한다. 배포일마다 배포되는 개발물의 갯수를 출력하시오.
- 입출력 예 :
progresses | speeds | return |
[93, 30, 55] | [1, 30, 5] | [2, 1] |
[95, 90, 99, 99, 80, 99] | [1, 1, 1, 1, 1, 1] | [1, 3, 2] |
- 풀이 : *사실상 max는 배포일이고, cnt는 배포갯수다.
progreeses | 93 | 30 | 55 |
소요일 | 7 | 3 | 9 |
max | 7 | 7 | 9 |
cnt | 1 | 2 | 1 |
- 출력 : [2, 1]
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
class Solution {
public int[] solution(int[] progresses, int[] speeds) {
if (progresses.length == 1) {
return new int[]{1};
}
// Queue에 소요 시간을 순차적으로 넣어준다.
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < progresses.length; i++) {
int leftPer = 100 - progresses[i];
int days = leftPer % speeds[i] == 0 ? leftPer / speeds[i] : leftPer / speeds[i] + 1;
q.offer(days);
}
// Queue에서 하나씩 뽑아서 max일자와 비교
int cnt = 1;
int max = q.poll();
ArrayList<Integer> result = new ArrayList<>();
while (!q.isEmpty()) {
int cur = q.poll();
if (cur > max) {
max = cur;
result.add(cnt);
cnt = 1;
} else {
cnt++;
}
if (q.isEmpty()) result.add(cnt);
}
return result.stream().mapToInt(e -> e).toArray();
}
}
- 다른 사람이 풀이한 방식 :
import java.util.ArrayList;
import java.util.Arrays;
class Solution {
public int[] solution(int[] progresses, int[] speeds) {
int[] dayOfend = new int[100];
int day = -1;
for(int i=0; i<progresses.length; i++) {
while(progresses[i] + (day*speeds[i]) < 100) {
day++;
}
dayOfend[day]++;
}
return Arrays.stream(dayOfend).filter(i -> i!=0).toArray();
}
}
> 문제 자체가 사실상 시간 제한이 없다 시피했는데, 위와 같이 푸는 게 더 가독성이 있어 보였다.
> 문제를 좀 더 논리적으로 이해하도록 해야겠다.
💡 프린터
- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42587
- 문제 요약 : 프린터 대기열에 쌓인 문서들이 있다. 이 문서들엔 우선순위가 랜덤하게 주어져 있는데, 앞선 문서 보다 더 높은 우선순위의 문서가 있다면 해당 문서는 가장 뒤로 넘어간다. 내가 출력하고자 하는 문서의 인덱스가 주어질 때, 해당 문서는 출력 시 어디에 위치해 있는가?
- 풀이 : 큐를 사용해서 일단 문서들을 다 넣어두고, 하나씩 꺼내보았다. 그리고 스트림을 사용해서 더 큰 수가 있으면 뒤로 넘기고, 없으면 출력하는 방식을 취했다.
import java.util.LinkedList;
import java.util.Queue;
class Solution {
public int solution(int[] priorities, int location) {
Queue<int[]> printer = new LinkedList();
for (int i = 0; i < priorities.length; i++) {
printer.add(new int[]{i, priorities[i]});
}
int cnt = 0;
while (!printer.isEmpty()) {
int[] cur = printer.poll();
boolean hasBiggerPrior = printer.stream().filter(x -> x[1] > cur[1]).count() > 0;
if (hasBiggerPrior) {
printer.offer(cur);
} else {
cnt++;
if (cur[0] == location) return cnt;
}
}
return -1;
}
}
'자료구조, 알고리즘 > Do it! 알고리즘 코딩 테스트' 카테고리의 다른 글
2. 자료구조 - 정의, 선형 자료구조 (0) | 2023.01.20 |
---|---|
1. 코딩 테스트 준비하기 - 시간 복잡도와 논리 오류 잡기 (0) | 2023.01.20 |