[파이썬 알고리즘 문제풀이 입문] 이분탐색(결정알고리즘) & 그리디 알고리즘 - 침몰하는 타이타닉(그리디)

*문제 본문은 강의 내용과 관련되어 있어 자세하게 적지 않았습니다.

 

 

 

문제

유럽에서 가장 유명했던 유람선 타이타닉이 침몰하고 있습니다. 유람선에는 N명의 승객이 타고 있습니다. 구명보트를 타고 탈출해야 하는데 타이타닉에 있는 구명보트는 2명 이하로만 탈 수 있으며, 보트 한 개에 탈 수 있는 총 무게도 M kg 이하로 제한되어 있습니다. N명의 승객 몸무게가 주어졌을 때 승객 모두가 탈출하기 위한 구명보트의 최소 개수를 출력하는 프로그램을 작성하세요.

 

 

 

풀이

• 내 풀이

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
weight = list(map(int, input().split()))
weight.sort()
count = 0

for i in range(N):
    if weight[i] == -1:
        continue
    for j in reversed(range(N)):
        if i == j and weight[j] != -1:
            count += 1
            weight[j] = -1
            break
        
        if weight[i] + weight[j] <= M:
            count += 1
            weight[i] = -1
            weight[j] = -1
            break
    weight.sort()

print(count)

• 답안 : Python (List 사용)

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
weight = list(map(int, input().split()))
weight.sort()
count = 0

# weight이 비어있으면 while문이 멈추게 된다.
while weight:
    if len(weight) == 1:
        count += 1
        break
    
    if weight[0]+weight[-1] > M:
        weight.pop()
        count += 1
    else:
        weight.pop(0)
        weight.pop()
        count += 1

print(count)

- for문을 굳이 2개를 사용하지 않고도 해결할 수 있는 방법이 있다는 것을 알게 되었다.

- 하지만 List를 사용하는 것도 pop()을 시키면 빠진 부분으로 뒤에 있는 것들이 이동하는 작업을 하기 때문에 굉장히 비효율적이다.

- 이럴 때 사용하는 것이 deque()이다.

- deque()는 자료들이 이동하는 것이 아니라, 포인터가 이동하는 개념이기 때문에 상당히 효율적이다.

 

• 답안 : Python (Deque 사용)

import sys
from collections import deque
input = sys.stdin.readline

N, M = map(int, input().split())
weight = list(map(int, input().split()))
weight.sort()
weight = deque(weight)
count = 0

# weight이 비어있으면 while문이 멈추게 된다.
while weight:
    if len(weight) == 1:
        count += 1
        break
    
    if weight[0]+weight[-1] > M:
        weight.pop()
        count += 1
    else:
        weight.popleft()
        weight.pop()
        count += 1

print(count)

- deque를 사용하려면 → from collections import deque 가 필요하다.

- List와 동일하게 맨 뒤의 값을 빼낼 때는 pop()을 사용하지만, 맨 앞의 값을 빼낼 때는 pop(0)이 아닌 popleft()를 사용해준다.

 

• 답안 : Kotlin (내가 바꿔본 것 / 정확X)

import java.io.*
import java.util.*

fun main(args: Array<String>) = with(BufferedReader(InputStreamReader(System.`in`))){
    val (N, M) = readLine().split(" ").map { it.toInt() }
    var weight = readLine().split(" ").map { it.toInt() }.toMutableList()
    weight.sort()
    var count = 0

    while(weight.size > 0) {
        if(weight.size == 1) {
            count += 1
            break
        }

        if(weight[0]+weight.last() > M) {
            weight.removeLast()
            count += 1
        } else {
            weight.removeLast()
            weight.removeAt(0)
            count += 1
        }
    }

    println(count)
}

- Kotlin에서 리스트의 마지막 인덱스에 접근할 때 → last() 사용

- Kotlin에서 리스트의 마지막 값을 제거할 때 → removeLast()  또는 removeAt(리스트.size-1) 사용