[PCCP] Lv2: 구명보트(42885) 해설

문제

- 문제 링크: 구명보트

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

4) 

 

코드

(C언어)

solution 1)

solution 1

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(Java)

solution 1)

- N: people의 길이

- Arrays.sort(people)의 시간 복잡도: O(NlogN)

- 반복문은 최악의 경우 people 배열 끝까지 반복하므로 최종 시간 복잡도는 O(NlogN)

import java.util.Arrays;

class Solution {
    public int solution(int[] people, int limit) {
        Arrays.sort(people); // 몸무게를 오름차순으로 정렬
        int count = 0; // 필요한 보트 개수
        int i = 0; // 가장 가벼운 사람을 가리키는 인덱스
        int j = people.length - 1; // 가장 무거운 사람을 가르키는 인덱스
        
         while (i <= j) {
             // 가장 무거운 사람과 가장 가벼운 사람을 같이 태울 수 있으면 두 사람 모두 보트에 태움
             if (people[i] + people[j] <= limit) {
                 i += 1;
             }
             // 무거운 사람만 태울 수 있으면 무거운 사람만 보트에 태움
             j -= 1;
             count += 1;
         }
         return count;
    }
}

solution 2)

#include<>

solution 3)

#include<>

 

(Python)

solution 1)

- N: people의 길이

- people.sort(): O(NlogN)

- 반복문은 최악의 경우 people 배열 끝까지 반복하므로 최종 시간 복잡도: O(NlogN)

def solution(people, limit):
    people.sort() # 몸무게를 오름차순으로 정렬
    count = 0 # 필요한 보트 개수
    i = 0 # 가장 가벼운 사람을 가리키는 인덱스
    j = len(people) - 1 # 가장 무거운 사람을 가리키는 인덱스
    
    while i <= j:
        # 가장 무거운 사람과 가장 가벼운 사람ㅇ르 같이 태울 수 있으면 두 사람 모두 보트에 태움
        if people[j] + people[i] <= limit:
            i += 1
        # 무거운 사람만 태울 수 있으면 무거운 사람만 보트에 태움
        j -= 1
        count += 1
    return count

solution 2)

import

solution 3)

import

 

(JavaScript)

solution 1)

- N: people의 길이

- people.sort(): O(NlogN)

- 반복문은 최악의 경우 people 배열 끝까지 반복하므로 최종 시간 복잡도: O(NlogN)

function solution(people, limit) {
    people.sort((a, b) => a - b); // 몸무게를 오름차순으로 정렬
    let count = 0; // 필요힌 보트 개수
    let i = 0; // 가장 가벼운 사람을 가리키는 인덱스
    let j = people.length - 1; // 가장 무거운 사람을 가리키는 인덱스
    
    while (i <= j) {
        // 가장 무거운 사람과 가장 가벼운 사람을 같이 태울 수 있으면 두 사람 모두 보트에 태움
        if (people[j] + people[i] <= limit) {
            i += 1;
        }
        
        // 무거운 사람만 태울 수 있으면 무거운 사람만 보트에 태움
        j -= 1;
        count += 1;
    }

    return count;
}

solution 2)

import

solution 3)

import