[programmers] 구명 보트

programmers Lv.2 구명보트

원래 포스팅 계획이 없었는데,

도저히 포스팅을 참을 수가 없어서 추가 포스팅 하게 되었다.

문제 해석

탐욕법(greedy) 문제이다.

1. 사람들의 몸무게가 List형태로 주어진다 (1~50000명)
2. 구명보트의 무게 제한 limit이 숫자로 주어진다 (40~240kg)
3. 모든 사람을 구명보트에 실으려고 할 때, 최소한 몇 개의 보트가 필요한가?

처음 작성한 코드 => 시간 초과...

def solution(people, limit):
    boats = 0   # 사람이 탄 보트의 갯수
    people = sorted(people)

    while len(people) > 1: # 모든 사람을 구출 할때까지
        if people[0] + people[-1] <= limit:
            people.pop(-1)
            people.pop(0)
            boats += 1
        else:
            people.pop(-1)
            boats += 1 
         
    if len(people) == 1:
        boats += 1

    return boats

people 배열을 몸무게 순으로 배치한 다음,
가장 가벼운 사람과 가장 무거운 사람의 몸무게 합이
구명보트의 무게 제한보다 적다면 둘다 배열에서 제거하고 count+1
같이 태울 수 있는 사람이 없다면 무거운 사람만 제거하고 count+1
   => 결국 무거운 사람(2명을 태울 수 없는사람)부터 counting 해야
   	  효율적으로 태울 수 있다고 생각하였기 때문에, people 배열을
      오름차순으로 정렬하였고, pop(-1)을 사용하였다.

한참 고민하였으나, 도저히 개선방법이 떠오르지 않았다.
자료구조와 시간 복잡도 관련 포스팅들을 계속 찾아보다가,
"Deque"라는 것을 알게 되었다!!!

Deque란?

파이썬에서 queue는 FIFO(선입선출) 방식으로 작동되는데,
deque는 양방향으로 접근 가능한 queue 이다!!!
파이썬에서 deque를 사용하기 위해서는 다음과 같이 함수 호출을 해야 한다.

from collections import deque

Q. 여기서 만약 JavaScript로 문제를 풀어야 한다면...?

.....? 어떻게 해야 하지?
찾아보니 자바스크립트도 deque를 구현하는 방법이 있다고 한다.
아직 문제 해결이 덜 됐으니 포스팅 하단에 추가하도록 하겠다.

수정한 코드

나는 이제 deque라는 전설의 검을 얻었다. 다시 가보자.

from collections import deque
def solution(people, limit):
    boats = 0   # 사람이 탄 보트의 갯수
    people = deque(sorted(people))

    while len(people) > 1: # 모든 사람을 구출 할때까지
        if people[0] + people[-1] <= limit:
            people.popleft()
            people.pop()
            boats += 1
        else:
            people.pop()
            boats += 1 

    if len(people) == 1:
        boats += 1

    return boats

deque를 구성했기 때문에, pop(0) 대신 popleft()를 사용할 수 있게 됐다!
기존 코드에서 pop(0)을 사용할때마다 발생하던 O(n)의 복잡도가
이제 O(1)로 변경되었기 때문에, 효율성 테스트를 통과할 수 있게 됐다.

다른 사람의 코드 => 투 포인터 전략

사실 내가 처음에 시도하려던 방법은 사실 이 방법이었다.

def solution(people, limit) :
    answer = 0
    people.sort()

    boat = 1
    a = 0
    b = len(people) - 1
    while a < b :
    	boat += 1
        if people[b] + people[a] <= limit :
            a += 1
        b -= 1
    return boat

매우 비슷한 과정인데, while문에서 투 포인터를 활용해서 문제를 해결했다.
pop(0) (JavaScript에서는 shift()) 툴을 사용하지 않기 때문에,
O(n)의 시간복잡도가 발생하지 않는다!!!

a는 처음부터, b는 마지막부터 시작해서 각각 탐색을 하되,
첫 index와 마지막 index의 합이 limit 이하이면 count +1하고,
시작 index인 a도 +1을 해준다.

만약 limit을 넘는다면 마지막 index인 b를 -1 해준다.

a < b 조건문이 완료되었다면 모든 원소에 대해 탐색이 끝난 상황이고,
boat에는 몇 번 담기 작업을 했는지가 저장되어 있으므로 정답이 된다.

이제는 정말 CS지식 - 특히 자료구조에 대한 공부 없이는
효율성 테스트를 통과하기 어려운 문제들이 많이 등장하고 있다.
포스팅이 필요 없는 날에는 문제를 조금 더 많이 풀고, 그렇지 않은 날에는
하루에 한 문제만 풀더라도, 이렇게 포스팅 하는 형태를 이어가려 한다.

번외) JavaScript를 통한 deque의 구현

class Deque {
  constructor() {
    this.arr = [];
    this.head = 0;
    this.tail = 0;
  }
  push_front(item) {
    if (this.arr[0]) {
      for (let i = this.arr.length; i > 0; i--) {
        this.arr[i] = this.arr[i - 1];
      }
    }
    this.arr[this.head] = item;
    this.tail++;
  }
  push_back(item) {
    this.arr[this.tail++] = item;
  }
  pop_front() {
    if (this.head >= this.tail) {
      return null;
    } else {
      const result = this.arr[this.head++];
      return result;
    }
  }
  pop_back() {
    if (this.head >= this.tail) {
      return null;
    } else {
      const result = this.arr[--this.tail];
      return result;
    }
  }
}

let deque = new Deque();

어지럽다. 이래서 코테는 파이썬 파이썬 하나보다..