구명보트
문제 설명
무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.
예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.
구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.
사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.
제한사항
- 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
- 각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
- 구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
- 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.
입출력 예
| people | limit | return |
|---|---|---|
| [70, 50, 80, 50] | 100 | 3 |
| [70, 80, 50] | 100 | 3 |
풀이
from collections import deque
def solution(people, limit):
cnt = 0
people.sort()
q = deque(people)
while len(q) > 1 :
if q[0] + q[-1] <= limit:
q.pop()
q.popleft()
cnt += 1
else :
q.pop()
cnt += 1
if q:
remain = q.pop()
if remain <= limit:
cnt += 1
else :
cnt = -1
answer = cnt
return answer배울점
처음에 DFS로 풀어야하나 했지만, 생각 외로 시간 초과가 나지 않아서 다행이었던 문제였다. 이 문제의 핵심은 결국 크기 순서대로 정렬시킨 다음 이를 순차적으로 제일 가벼운 것 + 제일 무거운 것으로 해서 어차피 자리가 두자리 밖에 없기 떄문에 더한 값이 limit보다 크다면 무거운 것은 혼자 타야된다.
따라서 로직은 만약 졍렬된 큐에서 처음 값과 나중 값의 합이 limit보다 작으면 둘은 같이 타는 것이 제일 효율적이기 때문에 두 값을 q에서 추출하고 cnt를 하나 늘려줌. 아닐 경우, 나중 값만 추출하고 cnt를 하나 늘려준다. 마지막에 하나 남을 수 있기 때문에 이를 고려해서 모든 과정이 끝나고 하나가 남을 경우, cnt를 하나 늘려준다.
하지만, 이러한 풀이가 맞는지 찾아보던 중, 대부분이 이렇게 풀었지만, 투 포인터를 이용하여 풀 수도 있다는 것을 배웠다.
코드는 다음과 같다.
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로직 자체는 모든 구성원들이 한명 씩 보트를 탄다고 가정하고 이 경우의 cnt에서 두 명이 같이 타야 하는 경우의 cnt를 빼주는 것이다. 두명이 같이 타는 cnt를 구하기 위해서 투 포인터를 사용했는데
여기서 투 포인터란?
- 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘
- 정렬되어있는 두 리스트의 합집합에도 사용됨. 병합정렬(merge sort)의 counquer 영역의 기초가 되기도 합니다
라고 한다.
먼저 가장 큰 값을 b라고 정하고 이 값과 같이 탈 수 있는 가장 작은 값 a와 합을 구한다 합이 limit보다 클 경우, 그 다음 큰 값을 b로 잡고 다시 가장 작은 a와의 합을 비교 만약 같이 탈 수 있으면 가장 작은 a는 그 다음으로 작은 값으로 바뀌고 b또한 그 다음 큰 값으로 변환한다. (코드상에서는 인덱스지만 설명상)
점프와 순간 이동
- 문제 설명
OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈트는 건전지로 작동되는데, 순간이동을 하면 건전지 사용량이 줄지 않지만, 앞으로 K 칸을 점프하면 K 만큼의 건전지 사용량이 듭니다. 그러므로 아이언 슈트를 착용하고 이동할 때는 순간 이동을 하는 것이 더 효율적입니다. 아이언 슈트 구매자는 아이언 슈트를 착용하고 거리가 N 만큼 떨어져 있는 장소로 가려고 합니다. 단, 건전지 사용량을 줄이기 위해 점프로 이동하는 것은 최소로 하려고 합니다. 아이언 슈트 구매자가 이동하려는 거리 N이 주어졌을 때, 사용해야 하는 건전지 사용량의 최솟값을 return하는 solution 함수를 만들어 주세요.
예를 들어 거리가 5만큼 떨어져 있는 장소로 가려고 합니다.
아이언 슈트를 입고 거리가 5만큼 떨어져 있는 장소로 갈 수 있는 경우의 수는 여러 가지입니다.
- 처음 위치 0 에서 5 칸을 앞으로 점프하면 바로 도착하지만, 건전지 사용량이 5 만큼 듭니다.
- 처음 위치 0 에서 2 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 2) x 2에 해당하는 위치로 이동할 수 있으므로 위치 4로 이동합니다. 이때 1 칸을 앞으로 점프하면 도착하므로 건전지 사용량이 3 만큼 듭니다.
- 처음 위치 0 에서 1 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 1) x 2에 해당하는 위치로 이동할 수 있으므로 위치 2로 이동됩니다. 이때 다시 순간이동 하면 (현재까지 온 거리 : 2) x 2 만큼 이동할 수 있으므로 위치 4로 이동합니다. 이때 1 칸을 앞으로 점프하면 도착하므로 건전지 사용량이 2 만큼 듭니다.
위의 3가지 경우 거리가 5만큼 떨어져 있는 장소로 가기 위해서 3번째 경우가 건전지 사용량이 가장 적으므로 답은 2가 됩니다.
제한 사항
- 숫자 N: 1 이상 10억 이하의 자연수
- 숫자 K: 1 이상의 자연수
입출력 예
| N | result |
|---|---|
| 5 | 2 |
| 6 | 2 |
| 5000 | 5 |
def solution(n):
ans = 0
while n :
if n % 2 :
n -= 1
ans += 1
else :
n /= 2
return ans배울점
이지했다.
