[Coding Test] 프로그래머스 2단계 - 구명보트

 

📚 문제

✏️ 메모 

탐욕법

- 현재 상황에서 가장 좋은 것(최선의 선택)을 고르는 알고리즘. 

- 매 순간 최선의 선택만을 하기 때문에 시간 절약이 가능함. 

 

1. 선택절차 : 현재 상태에서 최적인 선택을 함. 이후에는 선택을 바꿀 수 없음. 

2. 적절성 검사 : 선택한 항목이 문제의 조건을 만족시키는지 확인. 조건을 만족시키지 않으면 해당 항목 제외. 

3. 해답 검사 : 모든 선택이 완료 되면, 최종 선택이 문제의 조건을 만족시키는지 확인. 

 

// limit 를 보고 가장 최댓값을 찾음. 
// sort 를 해야 함. 
// 80 70 50 50 이렇게 될 텐데. 
// 100 - 80 하면 20 . >> 거꾸로 돌아서 20 이 있나 찾음 없으니까 
// 80 자리를 바꿔주고, answer ++; 
// 50의 경우 다른 50이 있으니까 둘 다 false 로 바꾸고 answer ++ ;
// people array 의 숫자가 없어질 때까지 반복. 

 

>>>>>> 잘못 생각. limit 에 가장 가까운 최댓값 부터 생각을 해서 빼지 않고, 

               두 사람의 몸무게를 더해도 100에 가장 가까운 최댓값이기만 하면 되는데.

               무거운 사람부터 시작. 

 

✏️ 메모

투 포인터 알고리즘

- 리스트를 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘

- 선형 시간 복잡도를 가지므로 효율적임. 배열이나 리스트 크기에 비례하여 알고리즘의 수행시간이 증가함. 

>>> 가장 무거운 사람은 index people.length -1 을 가짐. 

>>> 가장 가벼운 사람의 idx 를 관리하며  가장 무거운 사람 + 가벼운 사람 <= 제한 무게 의 상황을 확인하면 됨. 

[Java/알고리즘] 투 포인터 알고리즘(Two Pointer Algorithm) 이해하기 -1 : 종류, 활용방안

 

🔎 문제해결

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;

        Arrays.sort(people);
        // 맨 뒤가 최댓값.

        int idx = 0;

        for (int i = people.length - 1;  i >= 0; i--) {
            // 만약 이미 보트에 탄 사람이면
            if(people[i] == 1) continue;

            // 가장 가벼운 사람 + 무거운 사람 <= 제한
            if (people[i] + people[idx] <= limit ) {
                people[i] = 1;
                people[idx] = 1;
                idx++;
                answer ++;
            } else {
                people[i] = 1;
                answer ++;
            }

        }
        return answer;
    }
}