Greedy Algorithm
문제
김과장과 박주임이 사무실 이사를 위해 짐을 미리 싸 둔 뒤, 짐을 넣을 박스를 사왔다. 박스를 사오고 보니
각 이사짐의 무게는 들쭉날쭉한 반면, 박스는 너무 작아서 한번에 최대 2개의 짐 밖에 넣을 수 없었고,
무게 제한도 있었다. 예를 들어, 짐의 무게가 60kg, 40kg, 70kg, 50kg 이고 박스의 무게 제한이
100kg이라면 2번째 짐과 4번째 짐은 같이 넣을 수 있지만 1번째 짐과 3번째 짐의 무게의 합은 130kg이므로
박스의 무게 제한을 초과하여 같이 넣을 수 없다. 박스를 최대한 적게 사용하여 모든 짐을 옮기려고 한다.
짐의 무게를 담은 배열 box와 박스의 무게 제한 limit가 매개변수로 주어질 때,
모든 짐을 옮기기 위해 필요한 박스 개수의 최소값을 return 하도록 movingBox 함수를 작성하세요.
입력
인자 1 : box
Number타입의 40 이상 240 이하의 자연수를 담은 배열
인자 2 : limit
Number타입의 40 이상 240 이하의 자연수
출력
- Number 타입을 리턴해야 합니다.
- 모든 짐을 옮기기 위해 필요한 박스의 개수의 최솟값을 숫자로 변환합니다.
주의사항
- 옮겨야 할 짐의 개수는 1개 이상 50,000개 이하 입니다.
- 박스의 무게제한은 항상 짐의 무게 중 최대값보다 크게 주어지므로, 짐을 나르지 못하는 경우는 없습니다.
입출력예시
let output = movingBox([70, 50, 80, 50], 100);
console.log(output); // 3
let output = movingBox([60, 80, 120, 90, 130], 140);
console.log(output); // 4수도코드
1. 일단 배열안을 정렬해야 탐색하는게 조금 더 수월해질 수 있기때문에 배열을 sort 정렬한다.
2. 배열안의 인덱스(짐)들 중 가장 작은 인덱스와 가장 큰 인덱스를 비교하여 limit에 담기는지 확인한다.
3. 만약 두 인덱스의 합이 limit에 담긴다면 두 인덱스를 한데 담아 배출한다.
4. 만약 두 인덱스의 합이 limit에 담기지 않는다면 가장 큰인덱스를 하나만 담아 배출한다.
5. 이 과정이 진행될때 마다 인덱스의 위치를 이동해가며 모든 인덱스에 대한 계산을 진행한다.
6. 계산을 진행하며 각 인덱스들이 담길 수 있는 박스의 수량을 파악한다.
7. 최종 박스의 개수를 출력한다.문제풀이 (Reference)
function movingBox(box, limit) {
let twoBox = 0;
let sortedBox = box.sort((a, b) => a - b);
let leftIdx = 0;
let rightIdx = sortedBox.length - 1;
while(leftIdx < rightIdx) {
if(sortedBox[leftIdx] + sortedBox[rightIdx] <= limit) {
leftIdx++;
rightIdx--;
twoBox++;
}else{
rightIdx--;
}
}
return box.length - twoBox;
}코드해석
일단 네가지의 변수를 생성해주는데, 차례대로
1. twoBox = 두개의 짐이 모두 담길 수 있을때 카운트 하는 변수
2. sortedBox = 주어진 box배열을 오름차순으로 정렬한 변수 (sort 메서드 이용)
3. leftIdx = (좌측 = 0번째 인덱스) 의 카운트를 하는 변수,
이 변수가 오를때 마다 인덱스가 우측으로 이동하며 다음 인덱스를 가리킨다.
4. rightIdx = (우측 = sortedBox.length-1) 의 카운트를 하는 변수,
이 변수는 내림을 하여 인덱스가 좌측으로 이동하며 다음 인덱스를 가리킨다.
의 역할을 하는 변수들을 생성해준다.
반복문을 사용해 전체 배열을 탐색한다, 반복의 조건은 leftIdx 가 rightIdx 보다 커질 경우,
반복은 종료된다.
일단 2번 sortedBox 배열을 이용할텐데, 이 배열안의 맨 좌측 인덱스와 우측 인덱스를 살펴본다.
만약, 두 인덱스의 합이 limit 보다 작거나 같다면, 두개의 짐이 모두 담길 수 있기에
(ex. 전체 짐 무게의 합이 100kg 보다 작거나 같다면)
leftIdx++ 로 좌측인덱스를 우측으로 한칸 이동시키고,
rightIdx-- 로 우측인덱스를 좌측으로 한칸 이동시킨다. 이렇게 되면 다음 인덱스들의 비교가 가능해진다.
그리고 두 짐이 모두 담겼기 때문에 twoBox++ 로 카운트를 해준다.
그리고 만약 두 인덱스의 합이 limit 보다 크다면? 한 짐밖에 넣을 수 없을것이다.
이때는 두 인덱스 중 큰 값인 rightIdx 만 담고 rightIdx-- 로
우측 인덱스만 좌측으로 한칸 이동시킨다. 담기지 않은 좌측 인덱스는 그대로 유지된다.
이런 방식으로 이동하고를 반복하며 두 짐이 한박스에 담길때만 twoBox에 카운트를 해준다.
그리고 반복이 끝나고 만들어진 twoBox를 이용해야 한다.
일단 전체 배열의 짐을 각자 한 상자에 담는다고 가정을 하자, 인자 box의 길이 그대로 상자를 만드는것이다
그리고 twoBox의 카운트만큼 상자를 빼주자, 왜 이렇게 할까?
입출력예시를 가지고 설명해보자면 [70, 50, 80, 50] 의 배열의 길이는 4 이다,
한 짐당 하나의 상자를 쓰자고 가정했으니 상자의 개수는 일단 4가 된다.
이 배열을 오름차순으로 정리하면 [50, 50, 70, 80] 이고 위의 코드대로 계산이 진행된다면
마지막 반복에서 50과 50의 합이 <= limit 에 해당이 되므로 이 식에서는 twoBox는 1이 될것이다.
이럴때, 총 박스의 개수 4에서 1을 빼면 3이 된다, 두개가 들어가는 짐을 하나로 보는것이다.
10개중 6개가 2개 1조로 한 박스에 들어간다면 박스는 7개만 필요할것이다, 이런식인것이다.
그러므로 총 box의 길이 에서 twoBox의 값을 빼면 결과를 얻을 수 있다.
Frontend Developer