[프로그래머스 레벨투] 구명보트 🛶

🔽 문제 링크

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

✍🏼 나의 수도 코드

  1) people 배열을 내림차순으로 정렬한다.
  2) 가장 무거운 사람과 가장 가벼운 사람을 더해서 리미트가 넘는지 확인한다.
  3) 리미트가 넘을 경우 가장 무거운 사람만 태워서 보낸다.
  4) 리미트가 넘지 않을 경우 가장 가벼운 사람을 같이 태워서 보낸다.
  5) 가장 무거운 사람이 리미트의 절반 혹은 그보다 작을 떄는 남은 사람 /2를 올림해 구명보수 개수에 더하고 리턴해준다.

👨🏻‍💻 나의 문제 풀이

// 효율성 통과 코드
function solution(people, limit) {
    people.sort((a, b) => b - a);
    
    let count = 0;
    
    let heaviestPos = 0;
    let lightestPos = people.length - 1;
    
    while(heaviestPos <= lightestPos){
        
        if(people[heaviestPos] <= limit / 2){
            count += Math.ceil((lightestPos + 1 - heaviestPos) / 2);
            break;
        }
        
        count++;
        if(people[heaviestPos] + people[lightestPos] <= limit){
            heaviestPos++;
            lightestPos--;
        } else {
            heaviestPos++;
        }
    }
    return count;
}

// 효율성 실패 코드
function solution(people, limit) {
    people.sort((a, b) => b - a);
    let count = 0;
    
    while(people.length > 1){
        let heaviest = people[0];
        let lightest = people[people.length - 1];
        
        if(heaviest <= limit / 2){
            count = count + Math.ceil(people.length / 2);
            break;
        }
        
        if(heaviest + lightest <= limit){
            people.shift();
            people.pop();
            count++;
        } else {
            people.shift();
            count++;
        }
    }
    return people.length === 1 ? count + 1 : count;
}

내 기준 시간복잡도가 같은 로직이라고 생각했으나, 첫번째 코드는 효율성이 통과되고 두 번째는 통과되지 않는다! 단순 연산이 배열 메서드를 쓰는것보다 빠르기 때문인걸까? 두고두고 생각해볼 문제...

👩🏻‍💻 다른 사람의 코드

function solution(people, limit) {
    people.sort(function(a, b){return a-b});
    for(var i=0, j=people.length-1; i < j; j--) {
        if( people[i] + people[j] <= limit ) i++;
    }    
    return people.length-i;
}

🍯 기억해둘 것들!

• 반복문에서 변수 두 개 만들기!
• 배열을 가공하는 것보다는 단순 변수에 할당된 값을 계산하는 것이 빠르다.