초니로그

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

문제 설명

사람들의 무게를 담은 배열과 구명보트 1개가 최대로 담을 수 있는 무게의 한계값(limit)이 주어짐

이를 토대로 필요한 구명보트 수의 최솟값을 구해야 함

단, 구명보트에는 최대 2명만이 탑승할 수 있음

풀이법 구상

무게 배열을 정렬하고, 가장 큰 값과 작은 값을 더해서 limit을 넘는지 안 넘는지를 토대로 개수를 구함

[큰 값과 작은 값을 더했을 때 limit 이하인 경우]

-> 두 사람(큰 값, 작은 값)이 보트 하나에 탔다고 치고, 큰/작은 값에 해당하는 인덱스를 한 칸씩 이동 + 새로운 구명보트 꺼냄(카운트 1 증가)

[큰 값과 작은 값을 더했을 때 limit 초과인 경우]

-> 한 사람(큰 값)만 보트에 태우고, 큰 값에 해당하는 인덱스를 한 칸 이동 + 새로운 구명보트 꺼냄(카운트 1 증가)

코드 구현 (Java)

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        Arrays.sort(people);
        int answer = 0;
        int idx = 0;
        for (int i=people.length-1; i>=idx; i--) {
            if (people[i]+people[idx] <= limit) idx++;
            answer++;
        }
        return answer;
    }
}

문제 URL : https://school.programmers.co.kr/learn/courses/30/lessons/138476

문제 설명

귤 크기를 의미하는 정수 배열이 주어짐

이 중 k개의 귤을 뽑아야 할 때, 크기의 종류 최솟값을 구해야 함

풀이법 구상

<틀린 풀이>

DFS를 활용하여 귤 크기 배열 내 부분 집합을 구하여 최솟값 갱신

-> n은 최대 100,000인데, dfs가 끝날 때마다 ch 배열을 전부 확인하게 되며 O(N^2)의 시간 복잡도를 가지게 됨

import Foundation

var answer = 100000
var ch:[Bool] = []

func solution(_ k:Int, _ tangerine:[Int]) -> Int {
    ch = Array(repeating: false, count: tangerine.count)
    dfs(0, tangerine, k)
    return answer
}

func dfs(_ v: Int, _ t:[Int], _ k: Int) {
    if(v == t.count) {
        var sizes = Set<Int>()
        var contain_cnt = 0
        for i in 0..<t.count {
            if(ch[i]) {
                contain_cnt += 1
                sizes.insert(t[i])
            }
        }
        if(!sizes.isEmpty && contain_cnt == k && answer > sizes.count) { 
            answer = sizes.count
        }
        
    } else {
        ch[v] = true
        dfs(v+1, t, k)
        ch[v] = false
        dfs(v+1, t, k)
    }
}

<정답 풀이>

딕셔너리를 통해 귤의 크기 별 개수를 정의

크기 별 개수를 기준으로 딕셔너리를 내림차순 정렬

딕셔너리를 돌며 개수와 종류 수를 누적합하며, 그 값이 k 이상이 될 경우 누적된 종류 수를 반환

(개수가 많은 것부터 탐색하므로 누적된 종류 수는 최소일 수밖에 없음)

코드 구현 (Swift)

import Foundation

func solution(_ k:Int, _ tangerine:[Int]) -> Int {
    var dict:[Int:Int] = [:]
    for t in tangerine {
        if(dict[t] == nil) { dict[t] = 1 }
        else { dict[t]! += 1 }
    }
    let s_dict = dict.sorted { $0.value > $1.value }
    
    var sum = 0
    var answer = 0
    for d in s_dict {
        sum += d.value
        answer += 1
        if(sum >= k) { return answer }
    }
    return answer
}