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

이번 문제는 정렬의 소중함을 느끼는 문제였고,

복잡하게 생각 안 하고 단순하게 생각해야지 풀 수 있었던 문제인 것 같습니다.

 

---

 

접근방법

이 문제는

• 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 구하는 문제
• 한 번에 최대 2명씩 밖에 탈 수 없다.

이러한 조건을 가지고 있는 문제입니다.

 

구명보트 개수의 최소값을 구하기 위해 가장 좋은 방법은

아마 다들 아실거에요. 초등학교 때 배웠나? 어렸을 때 배우 던 건데

종이에다가 풀어보라하면 대부분 자동적으로 손이 저절로 쓰고 있는 모습을 볼 수 있을 겁니다.

(이래서 수학이 중요한가봐요.)

 

예를 들면 people =[90, 80, 70, 50, 40, 20, 10]; limit=100이면

다들 종이에다가는 이렇게 풀지 않았을까요?

구명보트 문제는 위에 이미지 그대로 풀면 됩니다.

즉, 정렬을 하고, 양쪽 끝에서부터 더한 값이 limit보다 작거나 같은 것을 찾고 아니면 다음 거를 찾고

이러다 보면 결국에는 가운데에서 만나고 끝나겠죠.

이걸 코드로 작성하면 됩니다.

---

해결방안

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

해결방안 순서

1. people 배열을 내림차순으로 정렬하기
2. 변수 answer, lastP 초기값 설정하기
3. lastP >= answer이 될 때까지 while문 반복해서 answer값 구하기

 

 

1단계. people 배열을 내림차순으로 정렬하기

let sortP = people.sort((a, b)=> b-a);

이 문제에서 오름차순이 아닌 내림차순으로 정렬해야 됩니다.

풀다 보면 알겠지만 [70, 50, 80, 50] 이러한 경우에 애매해져서 그렇습니다.

큰 수부터 파악하는 게 문제 풀 때 편리해서 내림차순으로 정렬해주었습니다.

 

정렬은 sort()메서드를 사용해주었습니다.

• 오름차순 : sort(), sort((a,b)=> a-b)
• 내림차순 : sort((a,b)=> b-a)

테스트 1 (people = [70, 50, 80, 50]; limit=100;)
let sortP = people.sort((a, b)=> b-a); -> [ 80, 70, 50, 50 ]

 

 

2단계. 변수 answer, lastP 초기값 설정하기

var answer = 0;
let lastP = sortP.length-1;

while문에서 사용할 변수를 설정해주었습니다.

answer, lastP의 어떻게 쓰일 거냐면

• answer : 필요한 구명보트 개수의 최솟값 -> sortp[answer] 이렇게 사용할 예정
• lastP : sortP배열에서 마지막이 몇 번인지 체크 -> sortp[lastP]이렇게 사용할 예정

이렇게 쓰일 겁니다.

 

그래서 answer, lastP의 초기값 설정으로는

• answer = 0;
• lastP = sortP.length-1;

이렇게 해주었습니다.

 

 

3단계. lastP >= answer이 될 때까지 while문 반복해서 answer값 구하기

while(lastP >= answer){
    if(sortP[answer] + sortP[lastP] <= limit) lastP--;
    answer++;
}
return answer;

여기서는 while문을 사용해주었습니다.

while문 안에 왜 코드를 이렇게 썼는지는 밑에 코드 진행 예시를 보시면 아실 것 같아요.

테스트 1 (people = [70, 50, 80, 50]; limit=100;)
let sortP = [ 80, 70, 50, 50 ]

answer = 0;
lastP = sortP.length-1; -> 4-1 = 3
조건 : lastP >= answer -> 3>0 true임으로 while문 진행
if(sortP[answer] + sortP[lastP] <= limit) -> if(sortP[0] + sortP[3] <= 100) -> if(80 + 50 <= limit) -> false
answer++; -> answer = 1;

answer = 1;
lastP = 3;
조건 : lastP >= answer -> 3>1 true임으로 while문 진행
if(sortP[answer] + sortP[lastP] <= limit) -> if(sortP[1] + sortP[3] <= 100) -> if(70 + 50 <= limit) -> false
answer++; -> answer = 2;

answer = 2;
lastP = 3;
조건 : lastP >= answer -> 3>2 true임으로 while문 진행
if(sortP[answer] + sortP[lastP] <= limit) -> if(sortP[2] + sortP[3] <= 100) -> if(50 + 50 <= limit) -> true
if문이 true임으로 lastP--;  실행 -> lastP = 2
answer++; -> answer = 3;

answer = 3;
lastP = 2;
조건 : lastP >= answer -> 2>3 false임으로 while문 진행안함

answer = 3;

while문 조건 lastP >= answer에서 =이 왜 있는지는 테스트 2를 하시면 아실 것 같습니다.

 

---

프로그래머스 구명보트 해결방안 설명은 여기까지입니다.