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

김선종·2021년 11월 1일
0

알고리즘

목록 보기
4/5

문제설명

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

처음에 생각한 해결법

  1. 몸무게 리스트를 정렬한다.
  2. 제일 큰 몸무게를 가진 사람부터 보트의 제한 무게 - 내 몸무게 가 최소가 되는 사람을 고른다.
  3. 조건에 만족하는 사람이 있으면 두명을 리스트에서 pop하고 아니라면 나 혼자 리스트에서 pop한다 (보트를 탄다)
  4. 모든 사람이 보트를 탈 때 까지(리스트가 []이 될 때 까지) 반복한다

그리디 알고리즘 문제이기 때문에, 최선의 선택을 한다는 것을 보트의 무게를 꽉꽉채워서 보내는 것이라고 이해했었다. 하지만 이런식으로 코드를 작성한다면 O(n2)O(n^2)가 되어 효율성 테스트를 통과하지 못했다. (물론 정확성조차 맞지 못했지만)

그래서 이렇게 생각해 보았읍니다

  1. 몸무게 리스트를 정렬한다.
  2. 보트의 제한무게의 절반 이상인 사람과 절반 이하인 사람으로 리스트를 나눈다.
  3. 무게의 합이 보트 제한무게에 가장 근접하게 두 사람을 조합한다. 가벼운 사람들 리스트에서는 마지막 인덱스에서 부터 탐색하고, 무거운 사람들의 리스트에서는 처음부터 탐색한다.

이러면 O(n)O(n)이기 때문에 효율성은 문제가 없다고 생각했다. 하지만 이렇게 할 경우에,,, 가벼운 사람 두명이 보트를 타는 경우에 대해 고려하지 않는다는 문제가 있었다.

생각해보면, 가장 무거운 사람과 같이 탈 수 있는 사람중 가장 가벼운 사람은, 리스트 내의 그 누구와도 같이 탈수 있게 된다. (어차피 보트의 정원은 2명이기 때문)
그래서 중간에서 끝으로 탐색하지 말고 끝에서 중간으로 탐색하는 것이 가벼운 사람 두명이 보트를 타는 경우에 대해서도 고려할 수가 있다.

삼고초려 끝에 정답

  1. 몸무게 리스트를 정렬한다.
  2. 제일 무거운 사람과, 제일 가벼운 사람의 인덱스를 지정해서, 둘의 무게가 제한을 초과하면 무거운 사람은 보트를 태워서 보내고(이 사람은 그 누구와도 같이 탈 수 없음이 자명하다), 다음으로 무거운 사람을 조사한다.
  3. 만약 둘의 무게의 합이 제한 이하라면, 둘을 모두 보트에 태우고, 그 다음으로 무거운 사람, 가벼운 사람에 대해 조사한다.
  4. 모든 인원이 보트를 탈 때 까지 반복한다.
def solution(people, limit):
    
    people.sort()
    answer = 0
    right = len(people) - 1
    left = 0
    
    while left < right:
        if people[left]+people[right] <= limit:
            left +=1

        right -= 1
        answer += 1
           
    if left == right:
        answer += 1
        
    return answer

Retrospect

  • 프론트엔드로 직군을 가고싶지만 알고리즘의 이점 때문에 코테 언어로 파이썬을 선택했는데, 점점 파이썬 의존도가 낮은 코드를 작성하는 것 같다.
  • 이게 진짜 그리디가 맞나 싶다.
profile
개발자가 되고싶다 열심히하자

0개의 댓글