1. 문제 정보
2. 손코딩
3. 어려웠던 부분
4. 코드
5. 다른 사람의 풀이
6. 어떤 부분이 / 스택/큐 로직과 연결되는지?
1. 문제 정보
- 출처: 코딩테스트 연습 - 기능개발 | 프로그래머스 스쿨 (programmers.co.kr)
- 문제 설명
프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.
또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.
먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.
- 제한 사항
- 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
- 작업 진도는 100 미만의 자연수입니다.
- 작업 속도는 100 이하의 자연수입니다.
- 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.
- 입출력 예
| 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] |
- 입출력 예 설명
- 입출력 예 #1
첫 번째 기능은 93% 완료되어 있고 하루에 1%씩 작업이 가능하므로 7일간 작업 후 배포가 가능합니다.
두 번째 기능은 30%가 완료되어 있고 하루에 30%씩 작업이 가능하므로 3일간 작업 후 배포가 가능합니다. 하지만 이전 첫 번째 기능이 아직 완성된 상태가 아니기 때문에 첫 번째 기능이 배포되는 7일째 배포됩니다.
세 번째 기능은 55%가 완료되어 있고 하루에 5%씩 작업이 가능하므로 9일간 작업 후 배포가 가능합니다.
따라서 7일째에 2개의 기능, 9일째에 1개의 기능이 배포됩니다. - 입출력 예 #2
모든 기능이 하루에 1%씩 작업이 가능하므로, 작업이 끝나기까지 남은 일수는 각각 5일, 10일, 1일, 1일, 20일, 1일입니다. 어떤 기능이 먼저 완성되었더라도 앞에 있는 모든 기능이 완성되지 않으면 배포가 불가능합니다.
따라서 5일째에 1개의 기능, 10일째에 3개의 기능, 20일째에 2개의 기능이 배포됩니다.
2. 손코딩
- 입출력 예1 기준으로 상태 변화
- progresses [93, 30, 55]
- 1일차 [93 + 1, 30 + 30, 55 + 5] => [94, 60, 60]
- 2일차 [94 + 1, 60 + 30, 60 + 5] => [95, 90, 65]
- 3일차 [95 + 1, 90 + 30, 65 + 5] => [96, 120, 70]
- ....
1. 모든 요소가 100 이상이 될 때까지 반복하기 위한 조건을 설정하기 위해서 let length = 0; 변수를 선언한다.
2. 100이 넘는 요소의 갯수를 체크하고 결과값으로 리턴하기 위한 const answer = []; 변수를 선언한다.
3. 100이상이 넘는 요소의 갯수(length)가 progresses 길이와 같아 질때까지 while 반복문을 실행한다.
4. progress 길이만큼 돌면서 speeds 만큼 더해준다.
5. 더 하고 난 후 progresses[0]이 100이상을 넘어가는지 확인한다. -> 더 하고 난 후 progresses[length]이 100이상을 넘어가는지 확인한다.
6. progresses[0]이 100 이상을 넘는다면 -> progresses[length]가 100 이상을 넘는다면
7. 100이상이 넘는 요소가 몇 개인지 체크하기 위해 let count = 0; 변수를 선언해준다.
8. progresses 의 길이만큼 돌면서 100 이상인 것을 만날 때마다 count 변수에 1씩 더해준다.
9. 100 미만인 요소를 만나면 break를 걸고 8단계의 for 문을 빠져온다.
10. length에다가 count를 할당한다. => length를 5단계의 progresses[0]을 progresses[length]로 수정한다. 이미 100이 넘는 요소를 체크했다면 5단계에서 progresses의 첫 value가 100이 넘는지를 체크하는 것이 아니라 100을 체크하지 않았던 요소부터 100이 넘는지 체크 해야 하기 때문에.
11. answer 에다가 count를 push 해준다.
12. progresses[0]이 100 이상을 넘지 않는다면 3단계로 넘어가서 계속 반복하면서 progresses의 요소를 speeds의 요소씩 더해준다. -> progresses[length]이 100 이상을 넘지 않는다면 3단계로 넘어가서 계속 반복하면서 progresses의 요소를 speeds의 요소씩 더해준다.
13. length가 progresses 배열 길이와 같아진다면 while 반복문을 종료한다.
14. answer를 리턴한다.
- 생각 흐름
* 2 - 4 - 5 - 6 - 8 - ( 100이상 인것들을 몇 개인지 세서 answer 배열에다가 그 갯수를 집어넣어야 하는데 그렇다면 그 갯수를 업데이트 할 변수를 설정해야겠군! count라는 변수를 설정해줘야지 ) - 7 - 9 - 11 - ( 어? 100이 넘는 요소들은 이미 셌으니 세지 않은 인덱스부터 다시 count 를 업데이트 해야하는데 세지 않은 인덱스를 어떻게 알아낼 수 있지? 배열의[count] 로 다시 세기 시작해야한느 인덱스를 구할 수 있으니 length에다가 카운트 변수를 += 더해주면 되겠구나 ) - 1 - 10 - ( length는 계속 카운트한 만큼 더해질거고 결국 length는 progresses 배열의 길이만큼 되겠네? 그렇다면 이걸로 while 조건문을 설정하면 되겠다 ) - 3 - ( 5단계에서도 0번째 인덱스부터 100이 넘는지 체크할 게 아니라 progresses[length] 부터 체크하는 걸로 수정하면 되갰네 ) - 5 - 6 - 12 - 13 - 14
- 푼 시간: 1시간 25분 28초
3. 어려웠던 부분
- 손코딩 3단계와 10단계가 어려웠는데 while 반복문의 조건과 그 조건을 빠져나오기 위해서 어떤 설정을 더 해줘야 하는지 어려웠다.
- 12단계에서 요소의 값이 100이상을 넘지 않는 값을 만나면 다시 3단계부터 시작한다. 다시 만난 5단계에서 이미 100이 넘어서 그 요소를 체크하고 넘어갔다면 체크하지 않은 요소부터 count를 세야 하는데 그 부분을 어떻게 설정해줘야 하는지 어려웠다.
결론적으로 알고리즘 문제를 풀면서 내가 생각하기 어려워 하는 부분은
- 어떤 것을 변수로 설정하고 그 변수를 while 반복문을 빠져나오기 위한 조건으로 설정해야하는지 이다.
나는 로직을 짜다가 중간에 아 이 조건에 빠져나가기 위해서는 이런 변수가 필요하겠는데? 등등 생각이 나는데
그 말은 반복문을 빠져나오기 위해 어떤 조건을 설정해야하는지 한번에 생각나지 않는다는 것이다. 절대로!
그러니 너무 답답해 할 필요도 없고, 어려워 할 필요도 없다.
4. 코드
function solution (progresses, speeds) {
const copy = [...progresses];
let length = 0;
const answer = [];
while (length !== copy.length) {
for (let i = 0; i < copy.length; i++) {
copy[i] = copy[i] + speeds[i];
}
if (copy[length] >= 100) {
let count = 0;
for (let i = length; i < copy.length; i++) {
if (copy[i] >= 100) {
count++
} else {
break;
}
}
length += count;
answer.push(count);
}
}
return answer;
}5. 다른 사람의 풀이
function solution(progresses, speeds) {
let answer = [0];
let days = progresses.map((progress, index) => Math.ceil((100 - progress) / speeds[index]));
let maxDay = days[0];
for(let i = 0, j = 0; i< days.length; i++){
if(days[i] <= maxDay) {
answer[j] += 1;
} else {
maxDay = days[i];
answer[++j] = 1;
}
}
return answer;
}6. 이 문제의 어떤 부분이 스택/큐 문제에 해당하는지?
progresses 배열을 돌면서 100이 넘는 요소가 몇 개 있는지 찾아서 answer 배열에다가 넣어주기(push) 때문에 스택 문제??
잘 모르겠다...
'알고리즘' 카테고리의 다른 글
| [프로그래머스] n^2 배열 자르기 (0) | 2023.01.22 |
|---|---|
| [LeetCode] 스택 > 20. Valid Parentheses (0) | 2023.01.17 |
| [프로그래머스] 스택/큐 > 프린터 (0) | 2022.09.03 |