그리디 문제 #4. 침몰하는 타이타닉

*이 풀이는 인프런: 파이썬 알고리즘 문제풀이 강좌에 기반하였습니다.

 

 

 

 

내 풀이

 

1. 구명 보트를 최소개수로 태우기 위해서는 보트의 무게 제한에 가깝게 태워야한다.

 

2. 몸무게를 오름차순 정렬해서 가장 작은 값과 가장 큰 값의 합이 보트의 무게 제한을 넘는 지 확인하고, 넘는다면 무게제한에 들 수 있을 때까지 가장 큰 값의 인덱스를 하나씩 줄여나간다.

 

3. 무게 제한에 들었다면 구명보트의 수를 1 증가시키고, 가장 작은 값과 큰 값의 인덱스를 갱신시킨다.

그리고 해당 사람이 구명 보트에 탔다는 것을 알려주기 위해서 check배열의 값에 1을 넣어준다.

 

4. 위 반복문을 통해 2명씩 태운 보트의 수(cnt)를 구했고, 아직 타지 못한 사람은 check배열의 값이 0인 사람들이기 때문에 check.count( 0 )를 cnt에 더해주어 최종 보트의 수를 구한다.

 

import sys
#sys.stdin=open("input.txt","rt")

n,m=map(int,input().split())
heights=list(map(int,input().split()))

heights.sort()
small=0
big=n-1
check=[0]*n
cnt=0

while small<big:
    sum=heights[small]+heights[big]
    if sum<=m:
        cnt+=1
        check[small]=1
        check[big]=1
        small+=1
    big-=1
print(cnt+check.count(0))

 

 

 

 

강사님 풀이

 

import sys
from collections import deque
sys.stdin=open("input.txt","rt")

n,limit=map(int,input().split())
p=list(map(int,input().split()))

p.sort()
p=deque(p)
cnt=0
while p:
    if len(p)==1:
        cnt+=1
        break
    if p[0]+p[-1]>limit:
        p.pop()
        cnt+=1
    else:
        p.popleft()
        p.pop()
        cnt+=1
print(cnt)

 

 

 

 

배운 점

 

1.

pop(0) 연산은 스택의 첫번째 요소를 삭제하고 나머지 뒷 자료들을 앞으로 당겨야해서 O(N)이 소요된다.

덱의 popleft( ) 연산도 pop(0)처럼 첫번째요소를 뺀다는 의미와 같지만, 실제로 요소를 삭제하는 것이 아닌 첫번째 요소를 가리키던 포인터를 옆으로 옮겨주는 것이기 때문에 O(1)이 소요된다.

 

따라서 pop(0)을 사용하는 것보다 리스트를 덱으로 바꾸어 덱의 popleft( )연산을 사용하는 것이 좋다.