99클럽 TIL (240809)

> [Middler] 구명보트

https://school.programmers.co.kr/learn/courses/30/lessons/42885?language=javascript

 

🔥다시보기🔥

걸린 시간 : 1시간 20분

 

오늘의 회고

그리디 문제라고만 생각하여 문제를 풀지 못했다. 다른 사람들의 풀이 방법을 참고하니 투 포인터를 활용하여 문제를 해결했다. 그렇다면 왜 이 문제는 그리디 문제로 분류가 되었을까? 

 

* 다른 사람들의 블로그를 읽어보니, 매번 가장 가벼운 몸무게, 가장 무거운 몸무게를 쌍으로 묶는 방법을 반복적으로 진행하면 '최적의 해'를 구할 수 있기 때문에 해당 문제가 그리디로 분류되었다는 것을 알수 있었다.

 

문제 분석

그리디 문제는 현재 상태에서 가장 좋은 것을 골라 '최적의 해'를 구하는 방법이다. 이 문제는 우선 투 포인터로 풀수 있다. 아직 스스로 다 풀지 못했다. 다음에 다시 도전해봐야 한다. 풀었을 때는 아래처럼 구현할 수 있다.

1.  people 을 (오름차순) 정렬한다.

2. start, end 포인터를 이용해 가장 가벼운 몸무게와 가장 무거운 몸무게를 가리킨다.

3. 가장가벼운 몸무게와 가장 무거운 몸무게를 합한 값이 limit 보다 작거나 같다면 둘을 보트에 태운다. 큰 경우에는 가장 무거운 몸무게 포인터를 - 1 한다.

4. 3번의 과정을 반복한다.

 

문제 풀이

1. python

def solution(people, limit):
    boat = 0
    # 정렬 후, 가장 작은 몸무게와 가장 큰 몸무게를 2개씩 짝지어서 limit와 비교한다.
    # 만일 합이 limit 보다 크다면
    
    start = 0
    end = len(people) -1 
    
    people.sort()
    
    while start <= end :
        # 합이 무게 제한보다 적다면 둘다 구출가능
        if people[start] + people[end] <= limit :
            start += 1
            end -= 1
        else :
            end -= 1
        boat += 1
    
    return boat

 

2. javascript

function solution(people, limit) {
    var answer = 0;
    
    // 몸무게를 정렬한다. -> 가장작은 몸무게와 가장 큰 몸무게를 합해 limit 보다 작거나 같다면 구명보트에 탄다.
    people.sort((a,b)=>a-b)
    
    while (people.length) {
        if (people[0] + people[people.length - 1] <= limit) {
            people.shift();
            people.pop();
            answer++;
        }else {
            people.pop();
            answer++;
        }
    }
    
    return answer;
}

 

시간복잡도 : O(NlogN)

정렬로 인해 O(NlogN) 시간복잡도를 가진다.

 

 

---

 

 

> [Beginner] 과일 장수

 

걸린 시간 : 15분

 

오늘의 회고

문제를 자세하게 읽고 원하는 대로 구현하면 답을 구할 수 있는 문제였다. 

 

문제 분석

과일장수가 최대 이익을 얻으려면, 사과의 최저점수가 가능한 가장 높아야한다. = 정렬 필요

모든 사과 점수 배열을 돌면서 1박스에 담을 수 있는 사과의 개수 (m)개 씩 잘라 이윤을 구해준다.

그리고 구한 모든 이윤을 더해 리턴한다.

 

문제 풀이

1. python

def solution(k, m, score):
    answer = 0
    
    # 과일장수가 최대 이익을 얻기 위해선, 사과의 최저점수가 가능한 높아야 합니다.
    # 사과 점수를 내림차순으로 정렬하고 m개의 사과박스를 만듭니다.
    # 그 중 최저 사과점수 * m * 상자의 개수 합을 구한다.
    
    score.sort(reverse=True)
    for i in range(len(score)) :
        if (i+1) % m == 0 :
            answer += score[i] * m * 1
    
    return answer

 

시간복잡도 : O(NlogN)

정렬로 인해 O(NlogN) 시간복잡도를 가진다.