[프로그래머스] Level2 구명보트(python)

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

프로그래머스

 

1. 내가 작성한 풀이

 

이진탐색 쓰면 되나? 라고 생각하긴 했지만 투 포인터를 이용했다.

 

1. 사람들을 몸무게를 기준으로 정렬시켜 준다.

 

2. 몸무게의 값이 제한 무게보다 큰 경우 그 위치부터 끝까지 아예 제외시킨다.

(문제의 조건에 구출할 수 없는 경우의 수는 없다고 나와있네욥ㅎㅎ)

 

3. start와 end를 이동시키며 2명씩 태울 수 있는 수를 조사한다.

- start는 people 중 가장 몸무게가 적게 나가는 사람을, end는 가장 많이 나가는 사람을 가리킨다.

- people[start] + people[end]가 limit보다 작다는 것은 end는 절대 둘이서 탈 수 없다는 것을 의미한다.

- 따라서 end 을 앞으로 이동시킨다(몸무게가 더 적은 사람을 가리키는 방향으로).

 

4. 3번을 반복하다 start+end가 limit보다 작거나 같아지는 경우가 생기면

- 사용한 구명보트의 개수(cnt)를 하나 늘리고

- 남아있는 people의 사람을 2명 줄여주고(2명은 구출했으니까)

- start와 end를 이동시킨다.

 

5. start가 end보다 커진 경우는 두 명씩 탈 수 있는 경우의 조사가 끝난 것이다.

- 따라서 남아있는 people는 구명보트의 제한무게보다 적지만 혼자 타야 하는 경우이므로

- cnt(현재 사용한 구명보트의 개수)  + 혼자서 타야하는 사람들의 수 를 return해준다.

 

 

def solution(people, limit):

    people = sorted(people)
    number = len(people)
    cnt = 0
    start = 0
    end = len(people)-1
    
    
    while start < end and number!=0:
        #제일 작은 값과 제일 큰 값이 limit보다 크면 end를 이동시켜줌
        if people[start] + people[end] > limit:
            end -= 1
        
        #limit보다 작으면 구명보트의 개수 +=1, start와 end 이동해서 제일 큰 값과 작은 값 갱신
        #남아 있는 사람 2명 적어짐
        else:
            cnt+=1
            number -= 2
            start+=1
            end-=1
            
    #남아있는 사람은 같이 탈 수 없는 사람이라 1개의 구명보트가 필요함
    #2명씩 태운 구명보트(cnt) + 1명 태운 구명보트(number)
    return cnt + number

 

 

3. 수정

def solution(people, limit):

    people = sorted(people)
    cnt = 0
    start = 0
    end = len(people)-1
    
    
    while start <= end: 
        if people[start] + people[end] > limit:
            end -= 1
            cnt+=1
    
        else:
            cnt+=1
            start+=1
            end-=1

    return cnt

 

유사한 방식이어도 더 쉽게 풀 수 있는 방법이 많은 것 같다