프로그래머스 #42586 기능개발

https://school.programmers.co.kr/learn/courses/30/lessons/42586

프로그래머스

 

 

이 문항은 3가지 정도 방법으로 스스로 풀어보았다.

 

스택을 이용한 풀이,

큐를 이용한 풀이,

그냥 풀이

이렇게 3가지이다.

 

---

풀이(1) 스택을 이용한 풀이

import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
    
        Stack<Integer> stack = new Stack<>();
        
        // 결과값을 담는 arrayList
        ArrayList<Integer> list = new ArrayList<>();

        int[] day = new int[progresses.length];
        int temp;

        // 며칠 후에 배포가 가능한지 담는 day 배열에 값 대입 (조건이 있는 이유는, 올림 때문)
        for (int i = 0; i < progresses.length; i++)
            day[i] = ((100 - progresses[i]) % speeds[i] == 0) ? (100 - progresses[i]) / speeds[i] : (100 - progresses[i]) / speeds[i] + 1;

        int i = 0;

        while (i < day.length) {
            temp = day[i];
            stack.push(temp);
            for (int j = i + 1; j < day.length; j++) {
                if (temp >= day[j]) {
                    stack.push(day[j]);
                } else {
                    list.add(stack.size());
                    stack.clear();
                    i = j;
                    break;
                }
            }
            
            /* 만약 temp >= day[day.length] 이면 stack에 push만 하고 list에 add하는 과정은 없다.
            따라서 stack에 아직 값이 있다면 list에 값을 add 해준다.
            */
            if (!stack.empty()) {
                list.add(stack.size());
                stack.clear();
                break;
            }
        }

        int[] answer = new int[list.size()];

        for (int k = 0; k < list.size(); k++)
            answer[k] = list.get(k);

        return answer;
    }
}

 

 

위에서 작성한 코드가 너무 깔끔하지 못해서

스택을 이용한 다른 풀이를 찾아보았다.

 

위에서 작성한 스택 풀이는,

temp을 포함해서 새로운 temp가 할당되기 전까지 수를 모두 스택에 넣고 clear()하는 등의 과정을 거쳤는데

아래 풀이에서는 temp는 없지만, 위의 풀이에서 temp 역할을 하는 수만 스택에 넣은 뒤

count을 result에 add해준다.

 

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        int n = progresses.length;
        int[] days = new int[n];
        ArrayList<Integer> result = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        
        // 위에서 조건문으로 작성한 코드를 ceil()을 이용해서 간단하게 코드를 작성할 수 있다.
        for (int i = 0; i < n; i++) {
            days[i] = (int)Math.ceil((100.0 - progresses[i]) / speeds[i]);
        }
        
        stack.push(days[0]);
        int count = 1; 
        
        for (int i = 1; i < n; i++) {
            if (stack.peek() >= days[i]){
                count++;
            } else {
                result.add(count); 
                stack.clear(); 
                stack.push(days[i]);
                count = 1; 
            }
        }
        
        result.add(count);
        
        int[] answer = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            answer[i] = result.get(i);
        }
        
        return answer;
    }
}

---

풀이 (2) 큐를 이용한 풀이

처음에 문제를 보고 큐를 이용해서 문제를 풀려고 했는데,

중간에 막혔었다.

 

그 이유는 중간에 while(!que.isEmpty() && temp >= que.peek()) 부분에서

&&를 쓸 생각을 못하고

이중 while문, 그러니까 여기서 맨 바깥의 while까지 포함해서 삼중 while문을 써야하나?

하는 생각 때문에 중간에 포기했다.

 

queue를 이용해 문제를 많이 안풀어봐서 이런 생각의 오류(?)가 발생한 거 같다.

 

그러다 스택으로 문제를 풀고난 뒤,

다른 사람들이 큐를 이용해 답안을 제출한 것을 보고 나도 다시 풀어보았더니 해결할 수 있었다.

 

큐를 이용한 풀이도 위의 스택을 이용한 풀이와 비슷하다.

 

여기서는 day의 모든 값들을 que에 넣어주고, 

temp가 que.peek()보다 크거나 같으면 poll을 해주면서 count값을 증가시키고,

temp가 que.peek()보다 작아지면 내부 while문을 멈춰준 뒤

count 값을 list에 add해준다.

 

이때 주의할 점은 내부 while 조건문에 temp랑 que.peek()이 같다는 조건, 

그니까 등호가 포함돼야 한다는 것이다!

 

나는 등호가 있는 케이스를 고려하지 못하고 등호를 안붙여서 실패를 경험했었다....

import java.util.*;
class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        Queue<Integer> que = new LinkedList<>();
        ArrayList<Integer> list = new ArrayList<>();

        int temp;
        int day;
        int count;

        for (int i = 0; i < progresses.length; i++) {
            day = ((100 - progresses[i]) % speeds[i] == 0) ? (100 - progresses[i]) / speeds[i] : (100 - progresses[i]) / speeds[i] + 1;
            que.add(day);
        }

        while (!que.isEmpty()) {
            temp = que.poll();
            count = 1;
            while (!que.isEmpty() && temp >= que.peek()) { // 등호!
                que.poll();
                count++;
            }
            list.add(count);
        }

        int[] answer = new int[list.size()];

        for (int k = 0; k < list.size(); k++)
            answer[k] = list.get(k);

        return answer;
    }
}

---

 

풀이 (3) 그냥 구현해본 풀이

프로그래머스 내에서 해당 문항이 스택/큐로 구분되어 있어서

스택이나 큐를 이용해서 문제를 풀어보았다.

 

스택이나 큐를 이용해야겠다는 생각에 사로잡혀서 다른 풀이는 고려하지 않았는데,

그냥 간단하게 풀 수 있는 문제였다.

 

스택과 큐만 이용하지 않았을 뿐 맥락은 위의 풀이들과 같다.

import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {        Stack<Integer> stack = new Stack<>();
        ArrayList<Integer> list = new ArrayList<>();

        // 작업 기간
        int[] day = new int[progresses.length];

        for (int i = 0; i < progresses.length; i++)
            day[i] = ((100 - progresses[i]) % speeds[i] == 0) ? (100 - progresses[i]) / speeds[i] : (100 - progresses[i]) / speeds[i] + 1;


        int count = 1;
        int temp = day[0];
        int i = 1;

        while (i < progresses.length) {
            if (temp >= day[i]) {
                count++;
            } else {
                list.add(count);
                count = 1;
                temp = day[i];
            }
            i++;
        }
        list.add(count);


        int[] answer = new int[list.size()];

        for (int k = 0; k < list.size(); k++)
            answer[k] = list.get(k);

        return answer;
    }
}