문제
마트에서 장을 보고 박스를 포장하려고 합니다. 박스를 포장하는 데는 폭이 너무 좁습니다. 그렇기에 한 줄로 서 있어야 하고, 들어온 순서대로 한 명씩 나가야 합니다.
불행 중 다행은, 인원에 맞게 포장할 수 있는 기구들이 놓여 있어, 모두가 포장을 할 수 있다는 것입니다. 짐이 많은 사람은 짐이 적은 사람보다 포장하는 시간이 길 수밖에 없습니다.
뒷사람이 포장을 전부 끝냈어도 앞사람이 끝내지 못하면 기다려야 합니다. 앞사람이 포장을 끝내면, 포장을 마친 뒷사람들과 함께 한 번에 나가게 됩니다.
만약, 앞사람의 박스는 5 개고, 뒷사람 1의 박스는 4 개, 뒷사람 2의 박스는 8 개라고 가정했을 때, 뒷사람 1이 제일 먼저 박스 포장을 끝내게 되어도 앞사람 1의 포장이 마칠 때까지 기다렸다가 같이 나가게 됩니다.
이때, 통틀어 최대 몇 명이 한꺼번에 나가는지 알 수 있도록 함수를 구현해 주세요.
입력
인자 1 : boxes
- Number 타입을 요소로 갖는, 포장해야 하는 박스가 담긴 배열
- 1 ≤ 사람 수 ≤ 10,000
- 1 ≤ 박스 ≤ 10,000
출력
- Number 타입을 리턴해야 합니다.
주의 사항
- 먼저 포장을 전부 끝낸 사람이 있더라도, 앞사람이 포장을 끝내지 않았다면 나갈 수 없습니다.
예시
만약 5, 1, 4, 6이라는 배열이 왔을 때, 5개의 박스를 포장하는 동안 1, 4 개의 박스는 포장을 끝내고 기다리게 되고, 6 개의 박스는 포장이 진행 중이기 때문에, 5, 1, 4 세 개가 같이 나가고, 6이 따로 나가게 됩니다. 그렇기에 최대 3 명이 같이 나가게 됩니다.
출력
const boxes = [5, 1, 4, 6];
const output = paveBox(boxes);
console.log(output); // 3
const boxes2 = [1, 5, 7, 9];
const output2 = paveBox(boxes2);
console.log(output2); // 1
문제를 이해한 나의 방식
원래 처음에는 문제 제대로 안봐서 인덱스 [0]의 일을 하는데 몇명의 인원이 필요한지 구하는 문제인줄알고 배열을 순회하면서 기준이 되는 값[0]에서 나머지 데이터들을 빼면서 포인트(max)를 찍는 형식으로 풀려고 접근했다.
근데 알고보니 테스트 케이스를 보니 내가 문제를 너무 어렵게 생각한 것 같아서 제대로 보니
그냥 일을 동시에 시작해서 같이 나갈수 있는 최대 인원수를 구하는 문제였다.
즉 그리디 알고리즘이므로 조금만 고민하면 쉽게 풀 수 있는 문제였다.
CODE
function paveBox(boxes) {
let result = 1; //인원 최소 값
let time = boxes[0]; // 비교할 임의의 데이터
let max = 1; // 리턴할 인원 최대 값
for(let i = 1;i<boxes.length;i++){
if(time >= boxes[i]){ // 일하는 시간이 더 큰사람들끼리 인원 묶기
result++;
}
else { // 일의 비용이 더 큰 사람을 만나면 인원 초기화, 시간기준 조정
result = 1;
time = boxes[i] // 시간 기준 바꿔버리기~ ** 핵심 **
}
max = result > max ? result : max; // 더 큰 인원무리를 max로 지정
}
return max; // 최대 인원 무리 반환
}
이 문제는 접근하기에 쉽고 재밌어 보이는 문제이기에 흥미를 가지고 풀어보았다.
이 문제에 관해 다른사람들 풀이를 봤는데 많은 함수를 사용해서 놀랐다.
slice()나 shift()를 쓰는 분도 있고 push()도 쓰셔서 조금 이해하는데 시간이 걸렸지만 그래도 색다른 풀이방법이라서 신기했다.
'Algorithm' 카테고리의 다른 글
백준 15649 N과 M (1) | 2022.12.22 |
---|---|
백준 2292 벌집 (0) | 2022.11.19 |
특정 거리의 도시 찾기(백준 18352) (0) | 2022.11.01 |
[C언어] 중복제거한 배열 출력 (0) | 2022.10.21 |
재귀(recursion) (0) | 2022.09.29 |