[프로그래머스] [Level 2] [탐욕법(Greedy)] 구명보트

문제) 구명보트 

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

 

• 내 풀이
  • 작은 값부터 정렬
  • 작은 값과 큰 값의 합이 limit 보다 작으면 두 명을 하나의 보트에 태운 것으로 간주
  • ⚠️ 정확성 테스트는 pass, 효율성 테스트는 fail

def solution(people, limit):
    n=len(people)
    answer = 0
    people.sort()
    for i in range(n):
        if people[i] > limit//2 and people[i]<limit:
            answer+=1
            continue
        elif people[i] > limit:
            continue
        for j in range(n-1,i-1,-1):
            if people[i]+people[j]<=limit: #가장 작은 값과 큰 값 부터
                answer+=1
                people[i]= limit+1 #이미 태운 사람 변경
                people[j] = limit+1
                break
            if j==i: #함께 탈 수 있는 사람이 끝까지 없으면
                answer+=1
    return answer

 

• 내 풀이2
  • min() , max() 이용
  • → 여전히 정확성 테스트는 pass, 효율성 테스트는 fail

def solution(people, limit):
    n=len(people)
    answer = 0
    while len(people)>=2:
        if min(people) > limit//2 and min(people)<limit:
            answer+=1
            people.remove(min(people))
            continue
        elif min(people) > limit:
            break
        if min(people)+max(people)<=limit: #가장 작은 값과 큰 값 부터
                answer+=1
                people.remove(min(people)) #이미 태운 사람 제거
                people.remove(max(people))
                continue
        answer+=1
        people.remove(max(people))
    if len(people)==1 and people[0]<=limit:
        answer+=1
        
    return answer

 

• 내 풀이3
  • 작은 값이랑 큰값 먼저 계산 안하고 
  • limit 값 내에서 값이 최대가 될 때 선택하도록 하는 방법
  • → 여전히 정확성 테스트는 pass, 효율성 테스트는 fail

def solution(people, limit):
    sum=0
    max_p=0
    max_idx=-1
    answer = 0
    for i,p in enumerate(people):
        if p==0 or p>limit:
            people[i]=0
            continue
        sum=p
        for idx,r in enumerate(people):
            if r==0 or i==idx:
                continue
            if sum+r>limit:
                continue
            if sum+r <= limit and max_p < sum+r : #합이 더 큰 값나오면
                if max_idx!= -1:
                    people[max_idx]=max_p-p #0으로 바꾼 값에 다시 원래 값 넣어주기
                max_p=sum+r
                people[idx]=0 
                max_idx=idx
        if max_p!=0:
            people[i]=0
            answer+=1
        max_p=0
        max_idx=-1
    n=len(people)-people.count(0)
    answer+=n
    return answer

 

 

 

• 다른 사람 풀이
  • 📍내 풀이가 틀렸던 원인
    • indexing으로 비교하는 것이 아니라 삭제나 값 수정 등 리스트 자체의 변경이 생기면 효율성 에러남
  • 가장 작은 값과 가장 큰 값의 합이 limit 보다 작으면 둘 다 태우고, limit보다 크면 큰 사람만 태움

def solution(people, limit):
    i=0 #가장 작은 값의 인덱스
    j=len(people)-1 #가장 큰 값의 인덱스
    answer = 0
    people.sort()
    while i<=j:
        answer+=1
        if people[i]+people[j]<=limit:
            i+=1
        j-=1
    return answer

 

• 다른 사람 풀이2
  • deque(데크)를 이용해서 people 값 전부 넣은 후
  • 가장 작은 값과 가장 큰 값의 합이 limit 보다 작으면 둘 다 pop, limit보다 크면 큰 사람 pop
    • queue: 선입선출 방식
    • deque: 양방향 큐 → 앞, 뒤 양쪽에서 추가 및 제거 가능
      • → 왼쪽: 앞 / 오른쪽: 뒤
      • append(): 가장 오른쪽에 삽입
      • appendleft(): 가장 왼쪽에 삽입
      • pop(): 오른쪽 끝 값 가져오면서 제거
      • popleft(): 왼쪽 끝 값 가져오면서 제거

from collections import deque

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

    # 보트는 2명씩만 탈 수 있고 무게 제한도 있음.
    q = deque(people)
    w = 0
    cnt = 0
    while q:
        if len(q) >= 2:
            if q[0] + q[-1] <= limit:
                q.pop()
                q.popleft()
                boat += 1
            elif q[0] + q[-1] > limit:
                q.pop()
                boat += 1
        else:
            if q[0] <= limit:
                q.pop()
                boat += 1
    return boat