[프로그래머스] 탐욕법(Greedy) _ 구명보트

2021_08_29 알고리즘 스터디 문제 풀이

문제 URL : https://programmers.co.kr/learn/courses/30/lessons/42885#

코딩테스트 연습 - 구명보트

 

문제

 

이 문제를 보고 든 생각은 우선 제일 무거운 순서대로 people 배열을 정렬하고, 제일 작은 요소를 순서대로 더했을 때 limit을 초과한다면 해당 요소들만을 같은 보트에 태우려고 했었는데 

문제에는 분명히 '한 번에 최대 2명씩 밖에 탈 수 없고'라는 내용이 포함되어 있다. 하지만 나는 이를 뒤늦게 알아서 처음에 좀 헛발을 딛었다.

1차 수도 코드

people을 sort로 내림차순 정렬하고, sortedPeople에 할당한다.

while문으로 sortedPeople.length 가 0이 될 때까지 수행한다
    sum + people[0]이 limit보다 작다면, 
        people shift 메소드로 앞에 있는 놈을 날린다
        sum = sum + people[0]
    그렇지 않고 같다면, result의 수를 1 증가시킨다
        people shift 메소드로 앞에 있는 요소를 제거한다
        sum = 0; sum 변수를 초기화 한다.
    초과하면서, 더이상 people에서 limit - sum보다 작은 게 없다면 result + 1 증가
		제일 앞에 있는 아이를 날리고 sum 변수 초기화

result를 리턴한다.

 

1차 문제 풀이

function solution(people, limit) {
    let sortedPeople = people.sort((a, b) => b - a);
    
    let sum = 0;
    let result = 0;
    
    while (sortedPeople.length > 0) {
        const tempSum = sum + sortedPeople[0];
        if (tempSum < limit) {
            sum += sortedPeople[0];
            sortedPeople.shift();
            if (sortedPeople.length === 0) {
                result++;
                break;
            }
        } else if (tempSum === limit) {
            result++;
            sortedPeople.shift();
            sum = 0;
        } else if (tempSum > limit && sortedPeople.findIndex((el) => limit - sum >= el) < 0) {
            sum = 0;
            result++;
        }
    }
    return result;
}

 

채점 결과

이때 2명만이 탑승할 수 있다는 지문을 인지하지 못한 상태였는데 정확성은 테스트는 모두 통과했지만, 효율성 테스트가 모두 실패로 뜨는 것을 보고 몰래카메라인가 했다.

while문 내부에서 findIndex 메소드를 통해 limit - sum 을 한 값보다 작은 요소가 있는 지 체크하는 조건이 작성 되어있어, 시간 복잡도 O(n^2)를 갖는 코드로 구현했다. 

하지만 findIndex를 사용하지 않으면, 대체 어떻게 더 작은 요소가 있는 지 확인을 하지않고 처리를 할 수 있는 지 생각이 나지 않았는데, 문제를 다시 읽어보니 해당 요구사항(2명만 탑승)이 명확하게 기재되어 있었고, 지문을 꼼꼼히 읽어야겠다는 반성을 하며, 2차 수도코드를 작성했다.

 

2차 수도코드

people을 sort로 오름차순 정렬하고, sortedPeople에 할당한다

while문으로 sortedPeople.length 가 0이 될 때까지 수행한다
    max는 sortedPeole의 인덱스 0의 값
    min은 sortedPeoPle의 마지막 인덱스 값
    
    만약, max + min의 값이 limit을 초과한다면,(같이 담을 수 없음)
        max만 담는다
        제일 앞에 있는 요소를 sortedPeople.shift()로 제거한다.
        result의 값을 1 증가시킨다.
        
    그렇지 않다면, (두개 다 담을 수 있음)
        shift, pop으로 제일 맨 앞, 맨뒤 두개의 원소를 제거한다.
        result의 값을 1 증가시킨다.
 
 result의 값을 리턴한다.

 

2차 문제 풀이

function solution(people, limit) {
    const sortedPeople = people.sort((a, b) => b - a);
    let result = 0;
    
    while (sortedPeople.length > 0) {
        const max = sortedPeople[0];
        const min = sortedPeople[sortedPeople.length - 1];
        
        if (max + min > limit) {
            sortedPeople.shift();
        } else {
            sortedPeople.shift();
            sortedPeople.pop();
        }
        result++;
    }
    return result;
}

 

채점 결과

people을 내림차순으로 정렬하게 되면, 맨 앞과 맨 뒤에는 제일 무겁고, 제일 가벼운 사람을 확인할 수 있다.

( 제일 무거운 + 제일 가벼운 )의 값이 limit을 초과한다면 제일 무거운 아이만 보트에 태워버리는 로직으로 구현했는데, 효율성 테스트에서 모두 시간 초과가 떴다. 아니 더 이상 어떻게 줄임? 하고 의문을 갖다가 하단 질문하기 페이지로 들어가 질문 내용들을 훑어봤다.

이 분은 다른 로직은 다 같았지만, 맨앞의 사람이 보트 제한 무게의 절반 이하가 되면, 무조건 맨 뒤의 사람과 같이 태워 보낼 수 있다. << 라는 이 부분이 내 코드와 상이한 부분이었다.

이렇게 세심하게 체크를 해야 하는구나 하고 감탄을 했고, 바로 3차 코드를 작성했지만 효율성테스트는 모두 떨어졌다.

문제 풀이

function solution(people, limit) {
    const sortedPeople = people.sort((a, b) => b - a);
    let result = 0;
    
    while (sortedPeople.length > 0) {
        const max = sortedPeople[0];
        const min = sortedPeople[sortedPeople.length - 1];
        
        if(max <= limit / 2) {
            result += Math.ceil(sortedPeople.length / 2);
            break;
        }
        
        if (max + min > limit) {
            sortedPeople.shift();
        } else {
            sortedPeople.shift();
            sortedPeople.pop();
        }
        result++;
    }
    return result;
}

 

shift와 pop 메소드를 통해서 분명 O(n)의 코드를 구현했음에도 처리가 되지 않아 다시 한 번 질문하기 탭을 확인했다.

분명 나와 똑같은 로직이나, shift, pop을 사용하지 않은, 인덱스 넘버로 매칭하여 처리하는 코드를 보았고,

shift 메소드를 통해서 배열의 제일 앞에 있는 요소를 제거하게 된다면, 남아있는 배열의 인덱스를 재배치하기위해 O(n)의 시간 복잡도가 소요된다는 사실을 고려하지 못했다.

직접 인덱스 넘버를 사용해서 배열의 변화 없이 처리하는 코드로 수정했다.

문제 풀이

function solution(people, limit) {
    let result = 0;
    const sortedPeople = people.sort((a, b) => b - a);

    let first = 0;
    let second = sortedPeople.length - 1;
    while (first <= second) {
        if (sortedPeople[first] <= limit / 2) {
            result += Math.ceil((second + 1 - first) / 2);
            break;
        }
        result++;
        if (sortedPeople[first] + sortedPeople[second] <= limit) {
            first++;
            second--;
        } else {
            first++;
        }
    }
    return result;
}

채점 결과

테스트를 모두 통과 했다.