[level 2] 구명보트 (파이썬 deque 복습)
문제
무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.
예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.
구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.
사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.
문제 풀이 접근법1
1) 이중 반복문을 사용하여 i와 j로 객체를 가리킴
2) for 문의 i번째 원소의 pair 몸무게를 pari 변수에 저장
3) 만약 i와 j가 다르고, pair = people[j]이면 짝을 찾은 것이므로 count에 1을 추가한다.
4) 이후, i번째와 j번째 원소를 "Pass"로 변경한다.
5) 문자열 pass의 개수를 count한뒤, 전체 길이에서 pass의 개수를 뺀다
6) 5의 값을 추가한뒤 count를 반환한다.
def solution(people, limit):
count = 0
for i in range(len(people)):
if people[i] != "pass":
pair = limit - people[i]
for j in range(len(people)):
if i != j and pair == people[j]:
count+=1
people[i], people[j] = "pass", "pass"
count += len(people) - people.count("pass")
return count연습 문제는 맞았는데 맞은게 없다..
근데 당연함. 문제를 잘못 이해하고 있었음 100이...안넘으면 되는거였구나 100 되어야 하는 줄
그리고 아무리봐도 큐나 스택으로 풀어야할 것 같긴함...일단 효율성이 있다는 점에서
+) 일단 저 코드를 기반으로 100이 넘지 않으면 사람을 추가하는 코드를 작성하여 보았다.
def solution(people, limit):
count = 0
for i in range(len(people)):
for j in range(len(people)):
if people[i] != "pass" and people[j] != "pass":
if i != j and people[i]+people[j] <= limit:
count+=1
people[i], people[j] = "pass", "pass"
count += len(people) - people.count("pass")
return count테스트 케이스 1, 3~7, 9~13번에서 실패했다.
효율성 테스트는 다 틀렸다.
문제 풀이 접근법2
1) i와 j가 다르고, people[i]와 people[j]가 pass가 아닌지 확인한다.
2) people[i]+people[j]의 값이 limit 보다 작거나 같은지 확인한다.
3) 만약 같다면, pepople[i]와 people[j]의 값을 pass로 바꾼뒤, count의 값에 +1을 한다.
4) count값에 현재 count *2한 값에서 people의 길이를 뺀 값을 더한다.
def solution(people, limit):
count = 0
people.sort()
for i in range(len(people)):
for j in range(len(people)):
if i != j and people[i] !="pass" and people[j] !="pass":
if limit >= people[i] + people[j]:
people[i], people[j] = "pass", "pass"
count +=1
count += len(people) - (count*2)
return count
똑같이 틀렸다....ㅎ
아 진짜 아무리 생각해도 모르겠어서
결국 구글링 엔딩..
다른 분들 풀이
다른 분들 풀이를 보니까 가장 많이 사용한 것이 파이썬의 덱(deque) 사용 혹은 end와 start를 가리키는 두 개의 포인터(투 포인터)를 활용한 풀이였다.
문제를 처음에 봤을 때 스택을 사용해야 할 것 같다! 까지는 생각했는데 여전히 내가 파이썬 자료구조에 어색...하고
정렬을 해야겠다! 까지는 생각했는데, 그 정렬된 자료구조의 앞 뒤에서 데이터를 빼내야 한다는 생각은 하지 못했다...
다른 분들 문제풀이1
from collections import deque
def solution(people, limit):
answer = 0
people = deque(sorted(people, reverse=True)) #내림차순 정렬 -> 덱
while len(people) > 1: #1명만 있으면 오류임(pop을 두번하니까..index 에러)
if people[0] + people[-1] <= limit:
answer +=1
people.pop() #최소값 pop
people.popleft() #최대값 pop(내림차순이므로 left에 큰 값 위치)
else:
answer+=1
people.popleft()
if people:
answer +=1
return answer
다른 분들 문제풀이2
해당 문제가 짝을 짓거나 아니면 혼자 타기 때문에 투 포인터도 가능하다!
def solution(people, limit) :
answer = 0
people.sort()
a = 0
b = len(people) - 1
while a < b :
if people[b] + people[a] <= limit :
a += 1
answer += 1
b -= 1
return len(people) - answer
파이썬 덱(deque)이란?
- double-ended queue의 줄임말, 양방향으로 넣고 뺄 수 있음
- 스택과 큐의 특성을 모두 가지고 있으며 둘을 조합한 형태의 자료구조
- 리스크가 O(n)의 속도를 가지는 반면 o(1)의 수행 속도를 가지고 있다는 특징을 가지고 있다.
알고리즘 시간에 교수님이 엄청 강조하셨던 것 중에 하나가 투포인터였던 것 같은데..
이게 막상 문제 풀이에서는 대충 이랬던 것 같음...까지만 기억나고 어케 문제 풀었는지는 기억이 1도 안남
하하.
암튼 중간고사 끝났으니 다시 열심히 문.풀 하겠습니다
[프로그래머스] LEVEL2 구명보트 (Python)
프로그래머스 알고리즘 풀이
velog.io