침몰하는 타이타닉 (그리디)
문제 정보는 인프런의 파이썬 알고리즘 문제풀이 코딩테스트에 있습니다!
문제풀이
n, limit = map(int, input().split())
p = list(map(int, input().split()))
p.sort()
cnt = 0
# p가 거짓이면 멈춤
while p:
# 마지막에 두 명이 남았을 때
if len(p)==1:
cnt+=1
break
if p[0] + p[-1] > limit:
p.pop()
cnt += 1
else:
p.pop(0)
p.pop()
cnt += 1
print(cnt)
마지막에 두명이 남았을 때의 경우까지만 생각해서 코드 짜기
deque라는 자료구조 활용하기
deque란 앞이나 뒤에서 값을 넣었다 뺄 수 있는데, 빼고 나서 바로 다음 자료구조를 가르키게 된다.
from collections import deque
n, limit = map(int, input().split())
p = list(map(int, input().split()))
p.sort()
p = deque(p)
cnt = 0
# 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)