프로그래머스 - 구명 보트 (Python)

lv. 2 단계의 코딩 테스트 연습 문제 중 '구명 보트'에 대한 풀이를 설명하고 있습니다.

 

프로그래머스 - 구명 보트 (Python)

 

코딩 테스트 연습 문제 풀이

 

1. 원리

2. 코드

위의 목차를 클릭하면 해당 글로 자동 이동 합니다.

 

원리

• 먼저, 이 문제에 대해 주의할 점을 얘기하자면 테스트 케이스 16 ~ 22까지는 문제에 나와있는 몸무게 제한인 40kg보다 작은 수들이 들어 있다.
• 따라서 40kg인 사람의 수를 array[40]에 기록하는 식으로 푸는 사람들은 탐색을 시작할 때 array[40]에서 시작할게 아니라 array[1] 에서 시작해야 한다...
• 최대 몸무게가 240kg이므로, 0~240 의 배열을 하나 만들고 0으로 초기화 한다 (생각하기 편하도록 241 크기의 배열을 만들어줬다).
• 그리고 사람들 몸무게를 하나씩 불러와서 기록한다.
  • 예를 들어, 50kg인 사람이 한 명 있으면, array[50] += 1 을 해주는 식이다.

array = [0 for _ in range(241)]
for p in people:
    array[p] += 1

• 이제 1kg부터 탐색을 시작한다.
• 1kg에 사람이 있다고 가정해보자
• 1kg을 보트에 태웠을 때, 짝꿍으로 태울 수 있는 가장 큰 몸무게의 사람은 보트의 최대 무게 제한인 (limit - 1)kg 이다.
• 따라서, diff 라는 변수에 나의 짝꿍이 될 수 있는 가장 큰 몸무게를 저장해두고, array[diff] 부터 -1씩 내려오면서 탐색을 한다.
  • 만약 array[diff]에 태울 수 있는 사람이 존재하면 array[diff] -= 1을 하고, 보트가 하나 완성되었으므로 보트의 수를 +1 한다. 즉, 바로 태워서 보트를 채운다.
  • 만약 array[diff]에 태울 수 있는 사람이 없으면, diff 에서부터 -1 씩 내려오면서 탐색을 한다.
  • 탐색을 하는 과정에서 사람을 찾으면 바로 태운다.
    • 첫 번째로 마주하는 값이 태울 수 있는 사람 중에서 가장 큰 몸무게이므로 바로 태우고 더 아래는 탐색할 필요가 없으므로, break 로 순회를 빠져나온다.
    • 근데 어디까지 순회하나? 바로 현재 타고 있는 사람인 1kg까지이다.
    • 이 이유는 1kg 이전까지는 사람을 모두 태워 보트를 만들었기 때문에 사람이 남아있을 수가 없다.
    • 또 1kg에 한 명 이상의 사람이 있는 경우 (1, 1) 이렇게 태울 수 있기 때문에 현재 타고 있는 사람의 몸무게까지 확인해야한다.
    • 만약 짝꿍을 찾지 못하는 경우에도, (1, ) 로 보트를 태워 출발시킬 수 있으므로 보트의 수를 +1 한다.
• 단순히 1kg 부터 +1 씩 하는 것이 아니라 1kg에 있는 사람이 다 없어져야 2kg을 탐색하는 과정으로 갈 수 있으므로 for문이 아니라 while문을 사용하고 idx (pointer 역할) 을 직접 관리한다.
• 해당 부분의 코드는 아래와 같다.

idx = 1
while idx <= 240:
    if array[idx] > 0:
        array[idx] -= 1
        diff = limit - idx
        if array[diff] > 0:
            array[diff] -= 1
        else:
            for i in range(diff, idx-1, -1):
                if array[i] > 0:
                    array[i] -= 1
                    break
        answer += 1

    else:
        idx += 1

• 아주 짧기 때문에 바로 이해할 수 있으리라 생각한다.
• 아래는 전체 코드이다.

코드

def solution(people, limit):
    answer = 0
    array = [0 for _ in range(241)]
    for p in people:
        array[p] += 1

    idx = 1
    while idx <= 240:
        if array[idx] > 0:
            array[idx] -= 1
            diff = limit - idx
            if array[diff] > 0:
                array[diff] -= 1
            else:
                for i in range(diff, idx-1, -1):
                    if array[i] > 0:
                        array[i] -= 1
                        break
            answer += 1

        else:
            idx += 1
    return answer

 

테스트 케이스를 똑바로 만들어 두는 것이 좋을 것 같다... 왜 프로그래머스는 이상한 테스트 케이스를 넣어놨을까??