[프로그래머스] LEVEL2 구명보트 (Python)

Loopy·2021년 7월 10일
6

프로그래머스

목록 보기
11/32
post-thumbnail

[프로그래머스] LEVEL2 구명보트


🧐 문제 설명


😍 나의 풀이

Greedy 알고리즘을 어떻게 사용할 것인가가 핵심인 문제. 보트를 가장 적은 횟수로 사람들을 이동시키려면 제일 무거운 사람, 제일 가벼운 사람을 같이 묶어서 처리해야한다는 게 핵심 아이디어다.

  1. people 리스트를 덱으로 만든 후 내림차순 정렬

  2. 무거운 사람(왼쪽)과 가벼운 사람(오른쪽)을 인덱스로 매칭

  3. 합이 보트 무게보다 가벼우면 둘 빼냄

  4. 보트 무게보다 무거우면 무거운 사람만 빼냄

from collections import deque

def solution(people, limit):
    answer = 0
    people = deque(sorted(people, reverse = True))
    
    while len(people) > 1:
        if people[0] + people[-1] <= limit: # 최댓값과 최솟값 묶어서 보트태움
            answer += 1
            people.pop()    #최소 빼내고
            people.popleft()    #최대 빼내고
        else:
            answer += 1
            people.popleft()
            
    if people:  #people에 1명 남아있는 경우 처리
        answer += 1
                
    return answer

👏 다른 사람의 풀이

def solution(people, limit) :
    answer = 0
    people.sort()

    a = 0
    b = len(people) - 1
    while a < b :
        if people[b] + people[a] <= limit :
            a += 1
            answer += 1
        b -= 1
    return len(people) - answer
  • 배울만한 코딩 SKILL
  1. 인덱스를 start, end 시점으로 투 포인터로 접근

  2. while문의 조건을 보면 인덱스 같아지는 시점(people의 모든 요소 다 조사됨)을 a<b로 표현한 것도 자주 보는데 난 잘 못 씀ㅠㅠ

  3. 또 return 값이 결국 len(people) - answer인 것은 전체 한 번은 옮겨야 하는데 가장 가벼운 것과 가장 무거운 것이 묶어서 되는 경우는 2명이 한 보트로 처리되기 때문에 전체에서 그 경우를 빼주려고 한 것 같다.


🥇 Today I Learn

Greedy (탐욕법, 탐욕 알고리즘)

Greedy Algorithm은 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식이다.

위의 그림에서는 가장 숫자가 큰 요소를 찾는데 있어서 해당 분기점마다 보다 큰 수를 찾는 방식으로 최종 해답을 찾아가고 있다. 순간마다 큰 수를 찾아가면 최종 결과는 12이다. 하지만 실제 전체 숫자 중에서 가장 큰 수는 99이다. 이처럼 전체 문제해결에서의 최적 해답을 찾지는 못한다.

하지만 이러한 단점들을 극복하는 Greedy의 가장 큰 장점은 계산 속도에 있다. 그래서 Greedy 방법이 통하는 몇몇의 문제에서는 최적해를 빠르게 산출해낼 수 있다.

투 포인터 (Two Pointer)

  • 배열 안에 있는 값들을 연속해서 더하거나 연산하는 경우에 사용 인덱스를 가리키는 두 개의 변수(포인터)를 선언하여 사용하는 특징이 있어 투 포인터라 불림

  • 예를 들어 N개의 숫자가 들어있는 배열이 주어질 때, 부분 집합의 합이 특정 숫자인 M인 경우의 수를 구하는 문제에 적용한다면, 배열의 인덱스를 가리키는 startPointer와 endPointer를 생성한 후 특정 규칙에 의해 각 포인터를 움직여 배열을 탐색해 문제를 해결할 수 있으며, 그 규칙은 다음과 같습니다.

    1-1) 현재까지의 합이 M보다 크거나 같은 경우 합에서 endPoiner가 가리키고 있는 값을 뺀 후 endPointer를 +1 증가시킵니다.

    1-2) 만약 startPointer의 값이 배열의 길이와 같을 경우 탐색을 종료합니다.

    1-3) 나머지 경우(현재까지의 합이 M보다 작을 경우)에는 합에 startPointer가 가리키고 있는 값을 더한 후 startPointer를 +1 증가시킵니다.

    2) 위의 세 규칙 중 해당하는 연산이 끝난 후 만약 현재까지의 합이 M과 같다면 답을 +1증가 시킵니다.

  • 투 포인터를 사용한다면 한 번 답이 될 수 없다고 판명된 이후의 값들을 더 이상 탐색하지 않으므로 시간 복잡도가 O(n)이 되어 완전 탐색에 비해 효율이 훨씬 좋음

profile
공부 쫌 해!!!😂

0개의 댓글