[프로그래머스/42586] 기능 개발
in Study / Coding Test
☑️ 문제
☑️ 풀이
첫 번째 시도 - Stack 사용
- 접근 방식
- 작업마다 완료까지 걸리는 날짜를 계산하고, Stack을 사용하여 같은 날 배포가 가능한 작업들을 처리하려고 시도했다.
- 마지막 작업을 어떻게 처리해야할 지 모르겠어서 따로 로직을 뺐다.
- 문제점
- 작업 완료일 계산에서 정수 나눗셈을 사용하였다. (예를 들어 2.4일이면 3일로 처리되어야 하는데 2로 처리됨)
- 마지막 작업 처리 방식의 비효율성이 존재하였다.
import java.util.*;
class Solution {
public int[] solution(int[] progresses, int[] speeds) {
int[] arr = new int[speeds.length];
for (int i = 0; i < speeds.length; i++) {
arr[i] = (100 - progresses[i]) / speeds[i];
}
int idx = 0;
Stack<Integer> stack = new Stack<>();
List<Integer> list = new ArrayList<>();
while (idx < arr.length - 1) {
if (arr[idx] >= arr[idx + 1]) {
stack.push(arr[idx]);
} else {
if (stack.isEmpty()) {
list.add(1);
} else {
int size = stack.size();
for (int i = 0; i < size; i++) {
stack.pop();
}
list.add(size + 1);
}
}
idx++;
}
// 마지막 작업 처리
if (stack.isEmpty()) {
list.add(1);
} else {
if (stack.peek() >= arr[arr.length - 1]) {
list.add(stack.size() + 1);
} else {
list.add(stack.size());
list.add(1);
}
}
int[] answer = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
answer[i] = list.get(i);
}
return answer;
}
}
두 번째 시도 - Stack 사용
- 접근 방식
- 동일하게 Stack을 사용하지만 마지막 작업까지 함께 처리하도록 했다.
- 첫 번째 시도에서는 Stack을
pop()하도록 했는데 여기서는clear()메서드를 사용하여 한 번에 Stack의 요소를 제거하도록 했다. - 또한,
Math.ceil메서드를 사용하여 실수는 올림처리 하도록 했다.
- 문제점
- Stack의 필요성이 명확하지 않았다.
- 여전히, 대부분의 테케를 통과하지 못하였다. → 특정 작업이 처리되지 않거나 중복될 가능성이 있는 것 같다.
import java.util.*;
class Solution {
public int[] solution(int[] progresses, int[] speeds) {
int[] arr = new int[speeds.length];
for (int i = 0; i < speeds.length; i++) {
arr[i] = (int) Math.ceil((100.0 - progresses[i]) / speeds[i]);
}
Stack<Integer> stack = new Stack<>();
List<Integer> list = new ArrayList<>();
for (int i = 0; i < arr.length; i++) {
if (stack.isEmpty() || stack.peek() >= arr[i]) {
stack.push(arr[i]);
} else {
list.add(stack.size());
stack.clear();
stack.push(arr[i]);
}
}
if (!stack.isEmpty()) {
list.add(stack.size());
}
int[] answer = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
answer[i] = list.get(i);
}
return answer;
}
}
세 번째 시도 - Queue 사용 (성공)
- 접근 방식
- 계산된 작업 완료일들을 Queue에 담아 순차적으로 처리하도록 했다.
- Queue의 FIFO(First In First Out) 특성을 이용하여 처음 들어온 작업부터 처리 가능하였다.
//시간: 0.44ms
//메모리: 77.6MB
import java.util.*;
class Solution {
public int[] solution(int[] progresses, int[] speeds) {
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < speeds.length; i++) {
queue.add((int) Math.ceil((100.0 - progresses[i]) / speeds[i]));
}
List<Integer> list = new ArrayList<>();
while (!queue.isEmpty()) {
int q = queue.poll();
int cnt = 1;
while (!queue.isEmpty() && queue.peek() <= q) {
cnt++;
queue.poll();
}
list.add(cnt);
}
int[] answer = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
answer[i] = list.get(i);
}
return answer;
}
}
☑️ 깨달은 점
- 문제 해결 과정에서 데이터 구조의 특성을 적절히 활용하는 것이 중요하다.
- Stack과 Queue의 차이를 잘 정리해두자.
