[프로그래머스 / 스택/큐 / 자바(JAVA)] 기능 개발

코딩테스트 - 프로그래머스/JAVA

[프로그래머스 / 스택/큐 / 자바(JAVA)] 기능 개발

읁; 2024. 4. 22. 19:30

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42586

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

[ 풀어보기 ]

오답 풀이

📌 로직

(100 - progresses[i] ) / speeds[i] 를 하면 해당 기능을 만드는 데 며칠이 소요되는지 알 수 있다.
- 위 나눗셈이 나머지가 있다면 올림을 한다.
- int 연산이므로 소숫점으로 나누어떨어지지 않기 때문에, 나머지가 있는 경우 +1 해준다.
progresses[i] 기능을 만드는 데에 소요되는 시간이,
progresses[i] 보다 먼저 있는 기능들의 소요시간 중
가장 시간이 많이 소요되는 기능 A의 소요시간보다 적으면
progresses[i] 는 A와 함께 출시된다.
- A의 소요시간을 max라고 가정한다.
- progresses[i]의 소요시간에서 max를 뺀다.
- 값이 음수이면 progresses[i] 는 A와 함께 출시되고, 양수이면 함께 출시되지 않는다.
로직을 짜보자면,
- Queue에 (progresses[i] 소요시간) - max 값을 넣는다.
- Queue를 순회하는 while을 만든다.
  - Queue에서 가장 상단의 값을 poll 한다.
  - Queue에 데이터가 아직 남아있고, Queue의 가장 상단 값이 0보다 작으면
    - 가장 상단값을 poll 한다.
    - 이렇게 poll 된 것의 개수를 세어서 return 배열에 차례로 집어넣는다.
- 이를 Queue에 데이터가 없을 때까지 반복한다.

📌 코드

import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {

        List<Integer> list = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();

        int max = 0;

        for(int i=0; i<progresses.length; i++) {

            if((100-progresses[i])%speeds[i]>0) {
                progresses[i] = (100-progresses[i])/speeds[i] + 1;
            } else {
                progresses[i] = (100-progresses[i])/speeds[i];
            }

            queue.add(progresses[i]-max);
            max = Math.max(progresses[i],max);

        }

        while(queue.size()!=0) {
            int n = 1;
            queue.poll();

            while(queue.size()!=0 && queue.peek()<0) {
                queue.poll();
                n++;
            }

            list.add(n);
        }

        return list.stream().mapToInt(i -> i).toArray();
    }
}

📌 채점 결과

정확성  테스트
테스트 1 〉    실패 (2.76ms, 78.9MB)
테스트 2 〉    실패 (2.40ms, 66.6MB)
테스트 3 〉    통과 (2.38ms, 75MB)
테스트 4 〉    실패 (2.12ms, 76.3MB)
테스트 5 〉    실패 (3.17ms, 88.9MB)
테스트 6 〉    통과 (3.33ms, 74.8MB)
테스트 7 〉    통과 (2.90ms, 80.6MB)
테스트 8 〉    통과 (9.00ms, 83.6MB)
테스트 9 〉    통과 (3.02ms, 81.3MB)
테스트 10 〉    통과 (6.92ms, 75.2MB)
테스트 11 〉    통과 (3.03ms, 72.8MB)

채점 결과
정확성: 63.6
합계: 63.6 / 100.0

정답 풀이

📌 로직

(100 - progresses[i] ) / speeds[i] 를 하면 해당 기능을 만드는 데 며칠이 소요되는지 알 수 있다.
- 위 나눗셈이 나머지가 있다면 올림을 한다.
- int 연산이므로 소숫점으로 나누어떨어지지 않기 때문에, 나머지가 있는 경우 +1 해준다.
progresses[i] 기능을 만드는 데에 소요되는 시간이,
progresses[i] 보다 먼저 있는 기능들의 소요시간 중
가장 시간이 많이 소요되는 기능 A의 소요시간보다 적으면
progresses[i] 는 A와 함께 출시된다.
- A의 소요시간을 max라고 가정한다.
- progresses[i]의 소요시간에서 max를 뺀다.
- ~~값이 음수이면~~ progresses[i] 는 A와 함께 출시되고, 양수이면 함께 출시되지 않는다.
- 값이 0이거나 음수이면 progresses[i] 는 A와 함께 출시되고, 양수이면 함께 출시되지 않는다.
  - 값이 0이면, A와 progresses[i]가 동시에 작업이 완료된다는 뜻. 이를 간과했다.
로직을 짜보자면,
- Queue에 (progresses[i] 소요시간) - max 값을 넣는다.
- Queue를 순회하는 while을 만든다.
  - Queue에서 가장 상단의 값을 poll 한다.
  - Queue에 데이터가 아직 남아있고, Queue의 가장 상단 값이 0보다 ~~작으면~~ 같거나 작으면
    - 가장 상단값을 poll 한다.
    - 이렇게 poll 된 것의 개수를 세어서 return 배열에 차례로 집어넣는다.
- 이를 Queue에 데이터가 없을 때까지 반복한다.

📌 코드

import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {

        List<Integer> list = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();

        int max = 0;

        for(int i=0; i<progresses.length; i++) {

            if((100-progresses[i])%speeds[i]>0) {
                progresses[i] = (100-progresses[i])/speeds[i] + 1;
            } else {
                progresses[i] = (100-progresses[i])/speeds[i];
            }

            queue.add(progresses[i]-max);
            max = Math.max(progresses[i],max);

        }

        while(queue.size()!=0) {
            int n = 1;
            queue.poll();

            while(queue.size()!=0 && queue.peek()<=0) {
                queue.poll();
                n++;
            }

            list.add(n);
        }

        return list.stream().mapToInt(i -> i).toArray();
    }
}

📌 채점 결과

정확성  테스트
테스트 1 〉    통과 (2.23ms, 73.6MB)
테스트 2 〉    통과 (2.19ms, 77.1MB)
테스트 3 〉    통과 (2.07ms, 75.3MB)
테스트 4 〉    통과 (1.87ms, 66.4MB)
테스트 5 〉    통과 (1.82ms, 76.3MB)
테스트 6 〉    통과 (1.88ms, 77.2MB)
테스트 7 〉    통과 (2.94ms, 80.3MB)
테스트 8 〉    통과 (2.72ms, 78.7MB)
테스트 9 〉    통과 (2.02ms, 73MB)
테스트 10 〉    통과 (2.28ms, 82MB)
테스트 11 〉    통과 (2.03ms, 78.8MB)

채점 결과
정확성: 100.0
합계: 100.0 / 100.0

[코드 개선]

 if((100-progresses[i])%speeds[i]>0) {
    progresses[i] = (100-progresses[i])/speeds[i] + 1;
} else {
    progresses[i] = (100-progresses[i])/speeds[i];
}

개인적으로 이 부분이 좀 지저분해보여서 개선을 해보려 한다...

1. 남은 일자 계산방법을 단순하게 하기

📌 로직

progresses[i] 가 100보다 작으면 speeds[i]를 계속해서 더하는 while문을 만들어준다.
- speeds[i]가 더해지는 횟수 n만큼 queue에 add한다.
Queue의 size가 0이 될 때까지 반복하는 while문을 만들어준다.
- 일단 Queue의 가장 상단 값 A를 poll 한다.
- A와 함께 출시될 기능들은 A 값보다 작거나 같다는 것을 이용해, 다음 while문을 만든다.
  - Queue의 가장 상단값이 A보다 작거나 같고, Queue에 데이터가 남아있으면 poll 한다.
  - 그리고 poll 된 데이터 수를 return 배열에 추가한다.

📌코드

import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        
        List<Integer> list = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        
        for(int i=0; i<progresses.length; i++) {
            int n = 0;
            
            while(progresses[i]<100) {
                progresses[i] += speeds[i];
                n++;
            }
            queue.add(n); 
        }
        
        while(queue.size()!=0) {
            int n = 1;
            int a = queue.poll();
            
            while(queue.size()!=0 && a >= queue.peek()) {
                queue.poll();
                n++;
            }
            list.add(n);
        }

        return list.stream().mapToInt(i -> i).toArray();
    }
}

📌 채점 결과

정확성  테스트
테스트 1 〉	통과 (3.05ms, 79.2MB)
테스트 2 〉	통과 (2.04ms, 71.2MB)
테스트 3 〉	통과 (2.27ms, 73.7MB)
테스트 4 〉	통과 (2.33ms, 71.4MB)
테스트 5 〉	통과 (2.77ms, 75.2MB)
테스트 6 〉	통과 (1.83ms, 74.7MB)
테스트 7 〉	통과 (2.01ms, 80MB)
테스트 8 〉	통과 (1.87ms, 78.3MB)
테스트 9 〉	통과 (2.78ms, 77.4MB)
테스트 10 〉	통과 (2.11ms, 76.3MB)
테스트 11 〉	통과 (2.51ms, 76.9MB)

채점 결과
정확성: 100.0
합계: 100.0 / 100.0

2. `double`과 `Math.ceil()`을 활용하기

📌 코드

import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {

        List<Integer> list = new ArrayList<>();
        Queue<Double> queue = new LinkedList<>();

        double max = 0;

        for(int i=0; i<progresses.length; i++) {
            double a = Math.ceil((double)(100-progresses[i])/(double)speeds[i]);

            queue.add(a-max);
            max = Math.max(a,max);  
        }

        while(queue.size()!=0) {
            int n = 1;
            queue.poll();

            while(queue.size()!=0 && queue.peek()<=0) {
                queue.poll();
                n++;
            }

            list.add(n);
        }

        return list.stream().mapToInt(i -> i).toArray();
    }
}

📌 채점 결과

정확성  테스트
테스트 1 〉    통과 (2.92ms, 77.6MB)
테스트 2 〉    통과 (2.55ms, 73.9MB)
테스트 3 〉    통과 (3.13ms, 79.7MB)
테스트 4 〉    통과 (3.57ms, 79.9MB)
테스트 5 〉    통과 (2.37ms, 80.2MB)
테스트 6 〉    통과 (2.44ms, 80.5MB)
테스트 7 〉    통과 (2.82ms, 75.9MB)
테스트 8 〉    통과 (2.64ms, 78.3MB)
테스트 9 〉    통과 (2.49ms, 72.5MB)
테스트 10 〉    통과 (2.23ms, 80.1MB)
테스트 11 〉    통과 (2.11ms, 73.2MB)

채점 결과
정확성: 100.0
합계: 100.0 / 100.0

[ 좋은 풀이 ]

김기준 님, 김세영 님, 감자머리 님, Leenamgyo 님 외 78 명

📌 코드

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();
    }
}

📌 해석

progresses = [ 93, 30, 55 ]

speeds = [ 1, 30, 5 ] 라고 가정하고 살펴보자.

for문이 작동하는 모습을 표로 보기

progresses[i]	progresses[i] + (day * speeds[i])	day++
93	93 + (-1 * 1) = 92	O ( day = 0 )
	93 + (0 * 1) = 93	O ( day = 1 )
	...	...
	93 + (6 * 1) = 99	O ( day = 7 )
	*93 + (7 1) = 100**	while문을 벗어남 ⇒ day++이 일어나지 않음

⇒ dayOfEnd[7] ++;

progresses[i]	progresses[i] + (day * speeds[i])	day++
30	30 + ( 7 * 30 ) = 240	while문을 벗어남 ⇒ day++이 일어나지 않음

⇒ dayOfEnd[7] ++;

progresses[i]	progresses[i] + (day * speeds[i])	day++
55	55 + ( 7 * 5 ) = 90	O ( day = 8 )
	55 + ( 8 * 5 ) = 95	O ( day = 9 )
	55 + ( 9 * 5 ) = 100	while문을 벗어남 ⇒ day++이 일어나지 않음

⇒ dayOfEnd[9] ++;

dayOfEnd는?

dayOfEnd[7] = 2

dayOfEnd[9] = 1

이 둘을 제외한 index의 값은 모두 0이다.

값이 0인 것을 제외한 값들을 모아 Array로 만들어주면 된다.

⇒ stream의 filter를 이용해, .filter(i -> i!=0) 으로 걸러내어 이를 toArray() 해준다.

[배운 점]

📌 Queue의 기본적인 사용 방법

https://eunzzzzz1.tistory.com/29

[JAVA] Queue(큐)의 개념 / Queue(큐) 클래스 기본적인 사용법 및 메소드

Queue? 자료구조 중, 선형 자료구조로 분류된다. 한 쪽 끝에서는 삽입만, 다른 한 쪽 끝에서는 삭제연산만 이루어지는 유한 순서 리스트. 가장 먼저 온 사람이 가장 먼저 작업을 보고 나가는 '대기

eunzzzzz1.tistory.com

'코딩테스트 - 프로그래머스 > JAVA' 카테고리의 다른 글

[프로그래머스 / 스택/큐 / 자바(JAVA)] 프로세스 (0)	2024.04.24
[프로그래머스 / 2019 카카오 개발자 겨울 인턴십 / 자바(JAVA)] 튜플 (0)	2024.04.23
[프로그래머스 / 해시 / 자바(JAVA)] 의상 (0)	2024.04.19
[프로그래머스 / 2018 KAKAO BLIND RECRUITMENT / 자바(JAVA)] [1차] 캐시 (1)	2024.04.18
[프로그래머스 / 연습문제 / 자바(JAVA)] 행렬의 곱셈 (0)	2024.04.15

현재글[프로그래머스 / 스택/큐 / 자바(JAVA)] 기능 개발

"Hello, Eunji!"