반응형
https://school.programmers.co.kr/learn/courses/30/lessons/42885
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제풀이
추억의 강 건너기 문제. 보통은 오름차 정렬을하고 가벼운 사람들 부터 차례대로 태우는것 부터 풀이를 생각하겠지만 최대한 가벼운 사람과 무거운 사람을 함께 태우는것이 문제 해결의 최적의 해이다.
문제에서 [40, 40, 160, 160, 240] 해당 테스트 케이스를 추가 해보자.
최대한 가벼운 사람과 무거운 사람을 함께 태우는 로직
from collections import deque
def solution(people, limit):
answer = 0
people.sort()
people = deque(people)
while people:
if len(people) >= 2 and people[0] + people[-1] <= limit:
people.pop()
people.popleft()
else:
people.pop()
answer += 1
return answer
print(solution([70, 50, 80, 50], 100)) # 3
print(solution([70, 80, 50], 100)) # 3
print(solution([40, 40, 160, 160, 240], 200)) # 3
최대한 가벼운 사람들 부터 함께 태우는 로직
from collections import deque
def solution(people, limit):
answer = 0
people.sort()
stack = deque()
for item in people:
stack.append(item)
if len(stack) >= 2:
if stack[-1] + stack[-2] <= limit:
stack.pop()
stack.pop()
answer += 1
else:
stack.pop()
stack.pop()
answer += 2
answer += len(stack)
return answer
print(solution([70, 50, 80, 50], 100)) # 3
print(solution([70, 80, 50], 100)) # 3
print(solution([40, 40, 160, 160, 240], 200)) # 4
새로 추가한 테스트 케이스에서 결과가 달라지는것을 확인 할 수 가 있다.
