프로그래머스 문제풀이/LEVEL 2

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

지나가던 개발자 2021. 10. 29. 22:58
반응형

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

 

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

무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5

programmers.co.kr

sort와 그리디 알고리즘을 사용하면 해결할 수 있는 문제입니다.

 

문제 접근법

  • 보트에 탈 수 있는 인원의 최대가 2명이라는것을 생각합니다.
  • 가장 베스트한 케이스는 가장 가벼운 사람과 무거운 사람이 탔을때 한계치를 넘지 않는것입니다.
  • 이를 위하여 sort를 사용합니다.
  • 앞과 뒤를 체크하기 위한 index 두개를 준비합니다.
  • 맨 앞 인원과 맨 뒷 인원의 무게 합이 한계를 넘는지를 체크합니다.
    • 한계를 안넘을 경우 두명을 태운것이므로 앞 인덱스를 증가시키고 뒤 인덱스를 감소시키고 answer을 1증가시킵니다.
    • 한계를 넘을 경우 무게가 한명을 태울수 밖에 없으므로 뒤 인덱스를 감소시키고 answer을 1증가시킵니다.
  • 위 과정을 앞 인덱스가 뒤 인덱스보다 작을동안 진행합니다.

아래는 코드입니다.

더보기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int solution(vector<int> people, int limit) {
    int answer = 0;
    int a = 0, b = people.size();
    
    sort(people.begin(), people.end());
    
    if(b == 1)
        return answer = 1;
    
    while(a < b)
    {
        if(people[a] + people[b - 1<= limit) 
            a++;
        
        answer++;
        b--;
    }
    
    return answer;
}
cs
반응형