구명보트 [ TIL ] [ Javascript ] [ 프로그래머스 ]

 

Problem

https://school.programmers.co.kr/learn/courses/30/lessons/42885

프로그래머스

파이썬으로 알고리즘 문제를 풀다보니 자바스크립트로 알고리즘 문제를 푸는 감이 떨어진거 같아서 문제를 풀기로했다.

 

---

Try

우선 배열을 오름차순으로 정렬하고 반복문안에서 배열인덱스와 배열 마지막인덱스를 더했을때 limit 보다 같다면 answer 변수를 1 씩 올려주기로 생각하고 실행에 옮겼다.

이때 고민하다가 떠오른 메소드가 pop() 메소드와 shift() 메소드였다.

 

 

// 최대 2명 탑승 가능, 최대한 많이 탈 수 있게
// 제한 무게를 넘지 않아야함
// 탐욕법 큰거부터 빼준다.
function solution(people, limit) {
  let answer = 0;
  let sortPeopleArray = people.sort((a, b) => b - a);

  console.log(sortPeopleArray);

  // 배열 오름차순 정렬
  // 반복문 안에서 해당 배열인덱스와 해당배열 인덱스 끝자리를 더했을 limit 보다 작거나 같으면
  // answer 의 값을 1 올려주고 해당 값들을 지워준다.
  // 아닌 경우 앞에 인덱스를 지워주고 answer 의 값을 1 올려준다.

  // while 에 sortPeopleArray.length 를 넣어 배열이 없어지면 0 이기 때문에 배열이 비게될때까지 반복한다.
  // 알아보니 shift() 는 pop() 과 다르게 가장 앞에 인덱스를 제거한다.
  while (sortPeopleArray.length) {
    console.log(sortPeopleArray);
    if (
      sortPeopleArray[0] + sortPeopleArray[sortPeopleArray.length - 1] <=
      limit
    ) {
      sortPeopleArray.pop();
      sortPeopleArray.shift();
      answer++;
    } else {
      sortPeopleArray.shift();
      answer++;
    }
  }

  return answer;
}

console.log(solution([70, 50, 80, 50], 100));

끙끙대면서 풀었으니 정답이 나올줄 알았지만 "시간 초과"가 발생했다.

알아보니 이번에 사용한 shift() 메소드 때문인 것 같다. 메소드 자체 시간복잡도가 O(n) 이기 때문에 지금 저 while 문은 O(n^2) 가 되어버려 시간초과가 나오는 것 같다.

 

방식을 바꿔 다른 메소드를 알아보던중 splice 도 O(n) 이라 사용할 수 없었고 slice 가 O(1) 이기에 사용해보기로 했다.

 

while (true) {
    // console.log("while : " + sortPeopleArray); // [80, 70, 50, 50]
    if (
      sortPeopleArray[0] + sortPeopleArray[sortPeopleArray.length - 1] <=
      limit
    ) {
    //   console.log("if: " + sortPeopleArray);
      sortPeopleArray = sortPeopleArray.slice(1, sortPeopleArray.length - 1);
      answer++;
    } else {
    //   console.log("else : " + sortPeopleArray);
      sortPeopleArray = sortPeopleArray.slice(1, sortPeopleArray.length);
      answer++;
    }
    if (sortPeopleArray.length === 0) {
      break;
    }
  }

 

코드를 바꿔 제출한 결과 오히려 "시간 초과" 가 더더더더더 늘어났다.

아무래도 slice 가 시간복잡도는 O(1) 이지만 값을 계속 재할당하다보니 시간복잡도가 늘어난 것 같다.

 

---

Solve

메소드를 sort 만 사용해서 푸는 방법을 생각했는데 방법은 아래와 같다.

  let j = sortPeopleArray.length - 1; // j 로 기준점을 만든다.
  for (let i = 0; i <= j; i++) {
    if (sortPeopleArray[i] + sortPeopleArray[j] <= limit) {
      j--;
    }
    answer++;
  }

결국 메소드를 사용하지 않고 변수를 따로 빼두어 사용하는 것이 방법이었다. 

반복문을 진행하며 맨앞의 인덱스와 맨 뒤의 인덱스의 합이 limit 보다 적거나 같으면 j를 줄여준다. (두명씩 보트에 타기 때문에 조건문에 해당한다면 총인원을 한명 줄이는 식으로)

결과적으로 카운트한 answer 를 리턴하면 정답이당 ㅎㅎ

 

 

---

What I Learned

 

알고리즘도 알고리즘이지만 오늘 배웠던건 shift() , pop(), slice(), splice() 를 사용함으로서 그것들의 시간복잡도를 알게되었다.

shift() : O(n)

pop() : O(1)

slice() : O(1)

splice() : O(n)

이런 시행착오를 겪으면서 시간복잡도관련해서 배우게 되는 것 같다. 

아직 모르는 메소드들이 많고 모르는게 많다. 알고리즘을 더 풀어보고 부딪히며 배워야할 것 같다.