코딩테스트 준비 - 프로그래머스Lv2: 구명보트 풀이 (파이썬)

---

프로그래머스: 구명보트 풀이

---

문제풀러가기

https://programmers.co.kr/learn/courses/30/lessons/42885?language=python3# 

코딩테스트 연습 - 구명보트

---

문제 분석

1. 보트에는 2명까지만 탈 수 있음.

2. 보트에는 무게 제한이 있음.

---

코드:실패(시간초과)

def solution(people, limit):
    people.sort()
    weight=0
    cnt=0
    while people:
        weight=people.pop()
        for i in range(len(people)):
            if weight+people[i]<=limit:
                people.pop(i)
                break
        weight=0
        cnt+=1
    return cnt

    #시간초과

처음에 pop()을 썼더니, 효율성 검사에서 시간초과가 떠서 실패했다.

---

코드: 성공

def solution(people, limit):
    people.sort()
    cnt=0
    left=0
    right=len(people)-1
    while left<=right:
        if left==right:
            cnt+=1
            break
        if people[left]+people[right]<=limit:
            left+=1
            right-=1
        else:
            right-=1
        cnt+=1
            
    return cnt

똑같은 원리로, pop을 빼고 코드를 짜주니 성공!!

---

코드 풀이

 

def solution(people, limit):
    people.sort() #제일 작은 숫자와 큰 숫자를 먼저 조합해야하므로, 정렬을 한다.
    cnt=0 #보트수 카운트
    left=0 #왼쪽에서 오른쪽으로 인덱스 이동시키는 변수
    right=len(people)-1 #오른쪽에서 왼쪽으로 인덱스 이동시키는 변수
    
    while left<=right: 
        if left==right: #같은 인덱스를 가르킬때
            cnt+=1
            break
        if people[left]+people[right]<=limit: #제일 작은숫자와 큰숫자를 조합했을때
            left+=1
            right-=1
        else: 
        # 제일 작은숫자와 큰숫자를 조합해서 limit을 넘기면, 
        # 큰 숫자는 어떤 숫자와 조합해도 limit을 넘기므로 빼주면서 cnt+1을 해준다
            right-=1
        cnt+=1
            
    return cnt