8. 침몰하는 타이타닉(그리디)

[문제 아이디어]

list에서 pop(0)을 하면 뒤에 있는 자료형을 하나씩 앞으로 가지고 오는 현산을 하게 되어 비효율적이다.

그래서 deque를 사용한다. 

 

deque는 자료형의 앞과 뒤에서 넣고 뺄 수 있다.

from collections import deque

p = deque(p)

#자료형의 제일 앞에것을 pop한다. 

p.popleft()

 

 

[문제 침몰하는 타이타닉(그리디)  ]

유럽에서 가장 유명했던 유람선 타이타닉이 침몰하고 있다. 이 유람선에는 N명의 승객이 타고 있다.

구명보트를 타고 탈출해야 하는데 타이타닉에 있는 구명보드는 2명 이하로만 탈 수 있으며, 보트 한 개에 탈 수 있는 총 무게도 M kg 이하로 제한되어 있다. N명의 승객 몸무게가 주어졌을 때, 승객 모두가 탈출하기 위한 구명보트의 최소 개수를 출력하는 프로그램을 작성하시오.

 

 

-입력설명

첫 번째 줄에 자연수 N(5 ≤ N ≤ 1000)와 M(70 ≤ M ≤ 250)이 주어진다.

두 번째 줄에 N개로 구성된 몸무게 수열이 주어진다. (단, 몸무게는 50이상 150 이하)

각 승객의 몸무게는 M을 넘지 않는다. (즉, 탈출을 못하는 경우는 없음)

 

-출력설명

첫 번째 줄에 구명보트의 최소 개수를 출력하시오.

 

-입력예제1

5 140
90 50 70 100 60

 

-출력예제1

3

 

import sys
from collections import deque
sys.stdin = open("input.txt", "rt")
'''
deque 를 사용하면 조금 더 효율적인 코드가 된다.

list 에서 pop(0)을 하면 뒤에 있는 자료형이 제일 앞으로 가지고 오는 연산을 하게 되어
비효율적일 수 있다.
'''
n, limit = map(int, input().split())
p = list(map(int, input().split()))

p.sort()
#p 가 deque 라는 자료구조형이 된다.
p = deque(p)
cnt = 0

#while 문 p가 비어있으면 거짓이 되어 멈춘다.
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)

 

*본 문제는 인프런 김태원 강사님의 파이썬 알고리즘 문제풀이 강의에 기반합니다.