[프로그래머스] 구명보트🛶 (Python) / level2 / 구현

Programmers Logo

 

 

Contents

 

---

 

1.  문제🔥

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

문제 설명

쉽게 말하면, 구명보트의 제한 무게에 맞춰 최대한 2명씩 태워서 구명보트의 개수를 최소화해서 출력하는 문제입니다.

1) 예제 입출력❄️

예제 입출력

people = [70, 50, 80, 50]이고, limit = 100 일 때, 몸무게가 70, 80인 사람은 혼자 태워 보내고, 50인 사람 2명을 태워 보내면 필요한 구명보트의 최소 개수는 3개입니다.

2. 핵심 논리☢️

주어진 people 리스트를 정렬하고, 리스트의 첫 번째 인덱스(0)와 마지막 인덱스(len(people)-1)에 포인터를 설정해서 그 합이 limit 초과일 때와 limit 이하일 때 구명보트에 2명, 1명 태워가며 포인터를 이동시키는 게 핵심입니다.

3. 풀이✅

1) 코드🌈

def solution(people, limit):
    answer=0
    people.sort()
    i=0;j=len(people)-1
    while i<=j:
        if people[i]+people[j] <= limit:
            i+=1;j-=1
            answer+=1
        else:
            j-=1
            answer+=1
    return answer

answer는 구명보트의 개수를 저장하는 변수입니다. 사람들의 몸무게 리스트 people을 정렬시켜주고 첫 번째 인덱스와 마지막 인덱스를 각각 i와 j에 초기화시켜줍니다.

인덱스 i는 오른쪽으로 움직일 것이고, j는 왼쪽으로 움직일 것이니 겹쳐지는 순간 끝나도록 while i <= j: 로 반복을 시작합니다.

people [i] + people [j]가 limit 이하이면 2명을 태워 보내니 i+=1;j-=1을 하고, people[i] + people[j]가 limit 초과이면 무거운 사람만 구명보트에 태워 보내니 j-=1을 합니다. 그렇게 구명보트에 태워 보낼 때마다 answer+=1을 해서 반환해주면 됩니다.

 

처음에 어떻게 풀어야 하나 이리저리 생각하다가, 오랜 시간이 지나 i와 j에 첫 인덱스와 마지막 인덱스를 저장해야지 라는 생각이 떠올랐습니다. 이건 비슷한 다른 문제들의 다른 풀이들에서 봤던 기억 때문에 떠올랐던 것 같습니다.

 

읽어주셔서 감사합니다.

다음에 더욱 유익한 글로 찾아오겠습니다.

 

* 관련 풀이 코드는 아래 깃허브 링크에 있습니다.

https://github.com/netsus/Programmers/blob/dd86dac3d8d8028bb6b9c650ad6ed22fc935be51/%5BAlgo%5D_Level2_%EA%B5%AC%EB%AA%85%EB%B3%B4%ED%8A%B8.ipynb

 

Reference)
1. Programmers Logo: https://programmers.co.kr/