[프로그래머스][level2] 구명보트 -python

문제 링크

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

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

 

풀이

- 그리디는 문제를 어떻게 풀지 다양한 아이디어를 고려해보아야 하는데 그걸 생각해내는 게 너무 어렵다. .. 

그리디 문제도 계속 풀면서 익혀야지 .. 

- 이번 문제의 아이디어는 

가장 큰 무게와 가장 작은 무게의 합이 limit보다 작다면 둘 다 태우고 

limit 보다 크면 큰 무게만 태운다는 것

- deque 를 사용해서 풀었다 

from collections import deque 

def solution(people, limit):

  # people 을 오름차순 정렬해서 deque 에 넣는다 
  q = deque(sorted(people))
  # 보트 개수 
  answer = 0 
  
  while q:
    # 길이가 1이면 보트 개수 +1 을 하고 끝 
    if len(q) == 1 :
      answer += 1 
      break 
    
    # 가장 큰 무게와 가장 작은 무게의 합이 limit보다 작거나 같으면 
    # 가장 큰 무게와 가장 작은 무게가 한 보트에 탈 수 있다면 
    if q[0] + q[-1] <= limit:
    # 큐에서 둘 다 제거 
      q.pop()
      q.popleft()
    else:
    # 큰 무게만 제거 
      q.pop()
    # 보트 수 + 1
    answer += 1 
  
  return answer

+ 2022.04.21 

- 배열로 풀이 

def solution(people, limit):
    answer = 0
    people.sort()
    start =0 
    end = len(people) -1 
    s = 0 
    
    while start <= end  :
		# 가장 큰 것과 가장 작은 것 둘 다 태울 수 있으면 
        if people[start] + people[end] <= limit :
        	# 둘 다 태움 
            start +=1 
            end -=1 
        # 아니면 큰 것만 태움 
        else :
            end -=1 
            
        answer += 1 
    
    return answer