프로그래머스) 구명보트

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

코딩테스트 연습 - 구명보트

나의 풀이)

이번 풀이는 내가 풀지 못하였다.

즉 질문하기 란에 사람들이 질문하고 답변한 것에서 힌트를 많이.. 얻어 풀었다는 뜻이다.

 

문제에 나와있듯 이 알고리즘은 탐욕법 알고리즘이다.

 

즉 모든 부분에서의 최적해를 구하는 것이 아닌 그 상황에서의 최적해를 구한다는 뜻이다.

 

나는 이중 for문, while문, 재귀 함수를 사용하여 테스트 케이스는 통과하였으나,

여러 방법을 사용하여도 정확성 20점, 효율성 10점의 처참한 점수를 얻게 되었다.. ㅠㅠㅠ

 

답답한 마음에 질문하기를 보았고 그곳에서 코드의 일부분을 보고야 말았다..!

 

결국 그 코드의 의도를 알게 되었고 의도에 맞게 코드를 작성한 결과 통과..

 

나는 아직도 탐욕법 알고리즘을 만났을 때 어떤 방법을 써야할지 모르겠다.

 

그저 많이 풀어보고 피드백을 얻는 수밖에는 없는 것 같다.

 

function solution(people, limit) {
    let answer = 0;
    let left = 0;
    let right = people.length - 1;
    
    people.sort((a, b) => a - b);
    
    while (left <= right) {
        if ((people[left] + people[right]) <= limit) {
            left += 1;
        }
        right -= 1;
        answer += 1;
    }
    
    return answer;
}

splice를 쓰지 않아도, 스택을 쓰지 않아도 되는 간결한 코드이다.

 

그저 더 풀어봐야겠다는 생각밖에 들지 않는다 ㅠㅠ