[Algorithms] 결정&그리디 알고리즘-침몰하는 타이타닉(그리디 알고리즘)

 

 

import sys
 
# sys.stdin = open("input", "rt")
n, limit = map(int, input().split())
weight = list(map(int, input().split()))
weight.sort()
 
cnt=0
while weight:                          # 리스트에 아무도 없으면 while문 탈출
    if len(weight)==1:                 # 마지막 한명이 남은 경우 두번째 if절에서 limit의 이하로 되버리면,
        cnt+=1                         # else 절에서 pop 할 때 오류가 발생하므로 한 명이 남은 경우의 조건을 따로 생성해,
        break                          # 오류를 방지해준다.
    if weight[0]+weight[-1] > limit:   # 하나의 보트에 2인 이하만 탑승 가능하다는 조건이 있으므로,
        weight.pop()                   # 가장 가벼운 사람 + 가장 무거운 사람의 경우를 생각해보면 된다.
        cnt+=1
    else:
        weight.pop()
        weight.pop(0)
        cnt+=1
print(cnt)

 

 

리스트가 아닌 덱을 사용한 방법은 더 효율적이다

리스트는 데이터가 pop 됐을 경우 다시 정렬을 하기때문에 비효율적 이지만

덱은 정렬은 그대로 유지한 채로 데이터를 가리키는 위치만 바뀐다 

import sys
from collections import deque          # deque 을 import 해온다
 
sys.stdin = open("input", "rt")
n, limit = map(int, input().split())
weight = list(map(int, input().split()))
weight.sort()
weight=deque(weight)
 
cnt=0
while weight:
    if len(weight)==1:
        cnt+=1
        break
    if weight[0]+weight[-1] > limit:
        weight.pop()
        cnt+=1
    else:
        weight.pop()
        weight.popleft()        # deque 에서는 가장 왼쪽의 element를 popleft()로 꺼내준다
        cnt+=1
print(cnt)