[김태원 알고리즘] 침몰하는 타이타닉 (그리디)

사용 언어: Python3

문제

풀이

내 풀이

N, M = map(int, input().split())
lst = list(map(int, input().split()))
visited = [False] * N # lst의 인원들이 구명보트에 탔는지 확인하는 용도
lst.sort()

cnt = 0
for i in range(N):
    if visited[i]:
        continue
    for j in range(N-1,i,-1): # 둘이 타는 경우
        if not visited[j] and lst[i] + lst[j] <= M:
            cnt += 1
            visited[i], visited[j] = True, True
            break
    else: # for~else # 혼자 타는 경우
        cnt += 1
        visited[i] = True
print(cnt)

다른 풀이 - 1. pop() 사용

N, M = map(int, input().split())
lst = list(map(int, input().split()))
lst.sort()

cnt = 0
while lst: # 가장 무거운 사람부터 탈출시키는데, 가벼운 사람까지 같이 탈 수 있으면 태운다고 생각
    if len(lst) == 1: # ✅ 예외 처리 꼼꼼히!
        cnt += 1
        break
    if lst[0] + lst[-1] <= M: # ✅ lst의 값이 하나일 때에는 0번째 원소와 -1번째 원소가 같은 값이기 때문에 논리 오류 발생 방지
        lst.pop(0) # 가장 가벼운 사람까지 같이 탑승
    lst.pop() # 가장 무거운 사람 탑승
    cnt += 1
print(cnt)

• 리스트는 pop(0)으로 맨 앞 원소를 꺼냈을 때, 뒤 원소들을 모두 한 칸 씩 앞으로 땡기기 때문에 비효율적

다른 풀이 - 2. deque 사용

from collections import deque # ✅

N, M = map(int, input().split())
lst = list(map(int, input().split()))
lst.sort()
lst = deque(lst) # ✅ 리스트를 deque 자료구조로 변환

cnt = 0
while lst:
    if len(lst) == 1:
        cnt += 1
        break
    if lst[0] + lst[-1] <= M:
        lst.popleft() # ✅ deque에서의 맨 앞 원소 꺼내기
    lst.pop()
    cnt += 1
print(cnt)

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기