[프로그래머스/JavaScript] 구명보트

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

프로그래머스

---

1) 풀이

이 문제는.. 진짜 며칠간 풀었었다

사실 풀고 나니까 와.. 진짜 별 거 아니었구나 싶은데 왜 그렇게 안 풀렸는지😂

 

처음에는 단순하게 그냥 구명보트 개수 변수 count, 현재 사람과 구명보트를 탈 수 있는 최대 무게 find, 그리고 현재 요소 cur을 변수로 두고 문제를 풀었다

그리고 효율성을 위해 내림차순으로 sort 시켰는데, 내림차순으로 한 이유는 그냥 제일 작은 요소부터 꺼내고 싶은데, shift()는 비효율적이라 pop() 을 사용하기 위해서!

people에서 pop으로 하나씩 빼서 해당 요소와 탈 수 있는 사람을 탐색해보는데, people에 해당 요소밖에 없었거나 find(cur과 구명보트 탈 수 있는 최대 무게)가 cur 보다 작거나 (내림차순으로 정렬되어 있기 때문에 현재 cur이 가장 작은 요소인데, 이것보다 find가 작다면 탈 수 있는 인원이 없음), 혹은 find가 40 미만이라면 바로 count++해주고continue 해준다

그 이후에는 find와 people 들의 요소를 하나씩 비교해서 find 보다 작거나 같은 요소를 찾는 처음 즉시 그 요소를 빼주고 count++해준다. (find로 집어넣을 사람이 없다면 그냥 count++만 해준다)

function solution(people, limit) {
    let count=0;
    let find=0;
    let cur=0;
    if(people.length===1) return 1;
    people.sort((a,b)=>b-a);
    while(people.length!==0){
        cur=people.pop();
        find=limit-cur;
        if(people.length===0||find<cur||find<40) {
            count++;
            continue;
        }
        for(let k=0;k<people.length;k++){
            if(people[k]<=find) {
                people.splice(k,1);
                break;
            }
        }
        count++;
    }
    return count;
}

이렇게 해주니까 모든 정답을 맞히는데, 효율성 1, 3번만 시간초과가 나왔다..!

그렇게 며칠동안 풀다가.. 도저히 이 두개의 시간초과를 해결하지 못해서 질문하기 를 찾아보니까 

출처: 프로그래머스 - 구명보트 질문하기 질문

이런 방법을 누가 제시해놓은 것!

그래서 나도 저런 방식으로 해보니.. 바로 정답..

그리디 문제라고 뻔히 적혀있었고, 2명이라고 뻔히 적혀있었는데 (사실 두개를 합치는 문제는 제일 큰 것과 작은 것을 비교해보는, 거의 그런 방식의 문제) 며칠동안 풀었던 게 허무하지만 그래도 이번주 넘기지 않고 풀어내서 다행이라 생각한다..

오늘의 큰 성과 (. ❛ ᴗ ❛.)

2) 최종 소스코드

function solution(people, limit) {
    let count=0;
    let find=0;
    let fir=0;
    let sec=people.length-1;
    people.sort((a,b)=>a-b);
    while(true){
        if(fir>sec) break;
        if(fir===sec) {
            count++;
            break;
        }
        find=limit-people[sec];
        count++;
        sec--;
        if(find>=people[fir])fir++;
    }
   
    return count;
}

3) 참고자료

https://school.programmers.co.kr/questions/15422

프로그래머스