[프로그래머스] level2. 구명보트(Greedy)

A. 문제설명

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

 

무인도에서 2명씩 보트를 타고 나가야 한다. 사람들의 몸무게가 주어지고, 보트의 제한 무게가 주어진다.

보트를 최소로 사용하는 횟수를 구한다.

B. 답안

from collections import deque

def solution(people, limit):
    answer = 0
    people.sort()
    boat = deque(people)
    
    while boat:
        small = boat[0]
        big = boat[-1]
        
        boat.pop()
        answer +=1
        
        if small + big <= limit:
            boat.popleft()
        
        if len(boat) == 1:
            return answer+1
    
    return answer

C. 회고

풀이과정은 이러했다.

 

1. 요구사항/ 제한사항 체크

- 배는 2명만 탈 수 있다

- 최솟값 구하기

- 1<= 사람 수 <= 50,000

 

2. 예제 만들어 경우의 수 확인

- [20, 30, 60, 70, 80, 90] : 정렬 후 맨 앞과 맨 뒤를 체크해도 문제 없겠구나. 왜냐면 정원이 2명이기 때문에 limit에 최대한 가깝게 타는게 정답이 된다. 

 

3. Big-O확인

- O(n^2)시 2,500,000,000 횟수가 나온다. 고로 이중 for문이 아니라 O(n)으로 해결해야한다.

 

4. 자료구조 / 기준/ 방향

- 자료구조: queue, stack

- 기준점: 제일 작은 몸무게를 기준으로. 제일 큰 몸무게를 기준으로 해도 상관 없음. 다만 코드 복잡성 증가.

- 방향: 양쪽 끝에서 안쪽 방향으로.

 

5. Pseudo 코드 작성

 

D. 회고

자료구조 선택시 queue를 쓰지 않아도, 배열을 선택했으면 조금 더 간단하다.

 

종료 조건이 작은인덱스가 큰인덱스보다 커지면 이기 때문에,

while small_index < big_index 식으로 인덱스로 접근하면 된다.

 

def solution(people, limit):
    answer = 0
    people.sort()
    small = 0
    big = len(people)-1
    
    while small < big:
        
        if people[small]+ people[big] <= limit:
            small +=1
        
        big-=1
        answer+=1
    
    return answer + 1 if small == big else answer

 

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        int small = 0;
        int big = people.length - 1;
        Arrays.sort(people);
        
        while(small < big){
        
            if(people[small] + people[big] <= limit)
                small++;
            
            big--;
            answer++;
        }
        
        if(small == big)
            return answer+1;
        else
            return answer;
    }
}