구명보트

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

프로그래머스

1차 작성 코드

function solution(people, limit) {
    let boatCnt = 0;
    let sum = 0;
    let lt = 0;
    
    people = people.sort((a,b)=>a-b)
    console.log(people)
    
    while(people.length !== 0){
        let firstEl = people.shift()
        // console.log(firstEl)
        if(sum<limit) sum += firstEl
        let nextEl = people[0]
        if(sum+nextEl>limit) {
            // console.log(sum+nextEl)
            boatCnt ++;
            sum = 0;
        }
        if(people.length === 1&&people[0]<limit) boatCnt ++;
    }
    
    return boatCnt;
}

 

2차 작성 코드

function solution(people, limit) {
    let boatCnt = 0;
    let sum = 0;
    let lt = 0;
    
    people = people.sort((a,b)=>a-b)
    console.log(people)
    
    for(let i=0; i<people.length; i++){
        let sum = boat.reduce((a,b)=>a+b, 0)
        if(sum<limit && boat.length <=1) boat.push(people[i])
        if(sum+people[i+1]>limit) {
            boatCnt ++;
            boat = [];
        }
        if(i===people.length-1&&people[i]<limit) boatCnt ++;
    }
    
    return boatCnt;
}

i 변수 하나만으로 작성하는게 적합하지 않다고 생각돼서, rt, lt를 사용하는 걸로 수정했다.

 

3차 작성 코드

function solution(people, limit) {
    let boatCnt = 0;
    let sum = 0;
    let lt = 0;
    
    people = people.sort((a,b)=>a-b)
    console.log(people)
    
    for(let rt=0; rt<people.length; rt++){
        sum += people[rt];
        if(sum <= limit && sum + people[rt+1] > limit) boatCnt++;
        while(sum > limit){
            sum -= people[lt++]
            if(sum <= limit) boatCnt++;
        }
    }
    
    return boatCnt;
}

구현하고 보니, sum이 최대 두 값만 계산돼야한다는 걸 고려하지 못했다는걸 깨달았다.

그러려면 sum을 배열로 구현해야하나.. 고민하다가 정답 풀이를 보는게 낫겠단 생각을 했다.

 

정답 코드

function solution(people, limit){
	var answer = 0
    people.sort((a,b) => b-a)
    let l = 0
    let r = people.length-1
    
    while(l<r){
    	var sum = people[l] + people[r]
        if(sum>limit){
        	l++
        } else {
        	l++
            r--
        }
        answer++
    }
    if(l == r) answer++
    return answer
}

계속 코드가 통과가 안돼서 정답 코드를 참고했다.

예전에 잠깐 배웠던 기억이 있는 다중 포인터 알고리즘!

나는 가장 가벼운 사람의 합을 먼저 구해나가는 방식으로 구현하려고 했는데,

정답 코드에서는 가장 무거운 사람과 가장 가벼운 사람의 합을 구해가면서,
left 변수를 0에, right 변수를 마지막 요소에 두고 두 변수를 이동시킨다.

 

=>

[30,50,70,80] / 제한 120일때

가벼운 사람 순으로 구하면 30,50/70/80 이지만

무거운 사람 + 가벼운 사람으로 구하면 50,70/30,80 으로 구할 수 있다.

 

 

 

참고

https://velog.io/@diddnjs02/코딩테스트프로그래머스-구명보트