[알고리즘 문제풀이] 프로그래머스 - 구명보트

yourjin·2022년 2월 27일

level2 알고리즘 탐욕법(Greedy)

알고리즘 문제풀이

목록 보기

4/28

TIL (2022.02.08)

➕ 오늘 푼 문제

프로그래머스 - 구명보트

➕ 아이디어

핵심 아이디어는 리스트를 정렬해서 가장 큰 값과 가장 작은 값을 같이 태우는 것이다.
- 가장 큰 값의 경우, 가장 작은 값이랑 함께 탈 수 없다면 혼자서 보트를 타야 한다.
  - 이 경우 혼자서 보트를 타고 다음 큰 값과 가장 작은 값을 함께 태울 수 있는지 확인한다.
- 같이 탈 수 있는 경우, 함께 보트를 타고 나간다.
  - 이 경우 다음 작은 값과 다음 큰 값을 함께 태울 수 있는지 확인한다.
- 남은 인원을 보트에 태운다.
  - 함께 타지 못하고 마지막에 홀로 남은 인원이 있을 수 있다. (start == end)

➕ Java 코드

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        int start = 0, end = people.length-1;

        Arrays.sort(people);

        while(start < end){
            if(people[start] + people[end] <= limit){
                // 두 명을 함께 보낼 수 있는 경우
                start += 1;
                end -= 1;
            }else{
                // 두 명을 함께 보낼 수 없는 경우
                end -= 1;
            }

            answer += 1;
        }

        // 남은 인원 보내기
        if(start == end){
            answer += 1;
        }

        return answer;
    }
}

➕ Python 코드

def solution(people, limit):
    answer = 0
    start, end = 0, len(people)-1

    people.sort()

    while(start < end):
        if people[start] + people[end] <= limit:
             # 둘이서 함께 탈 수 있는 경우
            start += 1
            end -= 1
        else:
            # 혼자 밖에 못 타는 경우
            end -= 1

        answer += 1
    
    if start == end:
        # 남은 인원 보내기
        answer += 1

    return answer