[Programmers] 구명보트

 

from collections import deque
def solution(people, limit):
    people.sort()
    deq = deque()
    for i in range (0,len(people)):
        deq.append(people[i])
    cnt = 0
    while len(deq) > 1:
        a = deq.popleft()
        b = deq.pop()
        if a + b <= limit:
            cnt += 1
        else:
            deq.appendleft(a)
            cnt += 1
    if len(deq) == 1:
        cnt += 1
    return cnt

 

덱을 사용하여 풀면 되겠다. 

알고리즘은 그리디 알고리즘.

 

덧붙여 한번 시간초과 뜨면서 한 방법이 있는데, 재귀 2번 돌리는걸로 했더니 효율성에서 개박살났더라 ...

 

결론적으로 아이디어는, 덱을 크기순으로 정렬해서 생성해준 뒤에,

덱의 길이가 1이상이 될때까지 반복 (1개가 남았을 경우에, while문 내에서 2개를 뽑아내지 못하기 때문)

 

만약 왼쪽에서 뽑은 값 (최소) 와 오른쪽에서 뽑은 값 (최대)가 limit 이하라면, 이 두개를 뽑아내면 되겠다.

 

여기서 중요했던 것이, 왜 이렇게 뽑는가? 였는데, 아래와 같다.

 

아마 많은 사람들을 태울 수 있다고 했다면 다른 방법으로 풀어야하지 않았나 싶기도하다.

혹은 while 안에 while을 하나 더 넣어야할 것 같다. 

 

from collections import deque
A = list(map(int,input().split()))
deq = deque()
for i in range (0,len(A)):
    deq.append(A[i])
N = len(deq)
limit = int(input())
num = 0
cnt = 0
while True:
    if deq == deque():
        break
    weight = deq.pop()
    num += 1
    while weight <= limit:
        if deq == deque():
            break
        a = deq.popleft()
        if a + weight > limit:
            deq.appendleft(a)
            break
        else:
            weight += a
            num += 1
        if num == N:
            break
    cnt += 1
print(cnt)

 

이런 느낌? 

Test case는 50 50 70 80 80, limit : 180으로 했는데 2로 맞게 나왔다 (80,50,50), (80,70)

 

토요일에 코딩테스트가 있는데 힘내서 보고 와야겠다.