Lv.2 구명보트

🤖문제

👍🏻 2022년 2월 12일

처음 코드

모든 테스트 케이스에서 정답이지만 효율성에서 시간초과가 남

<script>
  function solution(people, limit) {
      var answer = 0;
      people.sort((a,b) => b-a);    

      while(true) {
          let maxPerson = people.shift();
          let minPerson;
          let minPersonIdx;

          for (let i=0; i<people.length; i++) {
              if (people[i] <= (limit-maxPerson)) {
                  minPerson = people[i];
                  minPersonIdx = i;
                  break
              }
          }
          if (minPerson) people.splice(minPersonIdx, 1);
          answer++;

          if (people.length === 0) break
      }    
      return answer;
  }
</script>

왜 그럴까용?

입력예제처럼 [70, 50, 80, 50] 가 주어졌을 때 제일 처음에 maxPerson은 80이 되고 남은 배열을 for문으로 돌게 되는데 (limit - 80)인 20보다 작은 값이 없기 때문에 배열을 끝까지 돌게 된다.
이게 지금은 배열길이가 4니까 괜찮겠지만 배열 최대길이가 50000임을 감안해서 몸무게가 80인 사람이 50000명 있으면..!!! 효율성이 💩이다.

나름 효율성 고려해서 다시 짠 코드

하지만 이것도 효율성 통과 못 함 힝구

<script>
  function solution(people, limit) {
      var answer = 0;
      people.sort((a,b) => b-a);    

      while (people.length > 0) {
          let maxPerson = people.shift();
          for (let i=people.length-1; i>=0; i--) {
              if ((maxPerson + people[i]) <= limit) {
                  people.pop();
                  break
              } else break
          }
          answer++;
      }      
      return answer;
  }
</script>

이정도면 통과시켜줄만 한거 아닌가요 ㅜㅜ

다른 사람 코드 참고

<script>
  function solution(people, limit) {
      var answer = 0;
      people.sort((a,b) => b-a);

      let left = 0;
      let right = people.length - 1;

      while (left < right) {
          let sum = people[left] + people[right];

          if (sum > limit) {
              left++
          } else {
              left++
              right--
          }
          answer++;
      }
      if (left === right) answer++;
      return answer;
  }
</script>

내꺼 통과 못할 만 하다^^!!!
나는 왜 굳이 배열을 건드렸을까... 그냥 값만 더하면 되는 것을....
여전히 부족함을 느낀다~