🎯 Achievement Goals

프로그래머스 Lv2. 구명보트
코플릿 [DFS] 바코드

👉 프로그래머스 Lv2. 구명보트

문제 설명

무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.

예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.

구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.

사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

제한사항

무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.

입출력 예

people	limit	return
[70, 50, 80, 50]	100	3
[70, 80, 50]	100	3

🤔 나의 생각

이 문제는 일단 2명씩 밖에 탈 수 없다는 것이 가장 포인트였다.
먼저 계산하기 쉽게 나는 정렬을 하고 시작했다.
그리고 제일 작은 숫자부터 나머지 하나의 값을 찾아서 limit를 넘지 않는 선에서 구출해준다는 생각을 했다.
가장 작은 숫자랑 나머지 숫자를 더해서 비교해 봤을 때 limit 를 모두 넘긴다면 그 숫자는 하나만 구출되게 했다.
가장 중요한 점은 작은 숫자를 가지고 나머지 하나를 어떻게 찾을 것인가 였다.
일단 가장 작은 인덱스 0 과 가장 큰 인덱스 length-1을 할당했다.
그리고 정렬을 했기때문에 가장 작은 숫자와 가장 큰 숫자를 더해서 limit보다 작은지 찾을 수 있다.
작은 숫자와 큰 숫자를 더했을 때, limit 보다 크다면 max 인덱스를 1 줄여주고 카운트를 했다.
만약 원하는 값이 나왔다면 min 인덱스 1을 더해 다음으로 작은 값에 대해서 찾았다.

code

function solution(people, limit) {
    people.sort((a, b) => a - b);
    
    let min = 0;
    let max = people.length-1;

    while(min <= max) {
        if (people[min] + people[max] <= limit) {
            min += 1;
        }
        max -= 1;
        count += 1;
    }
    return count;
}

👉 코플릿 [DFS] 바코드

문제

1, 2, 3으로만 이루어진 수열 바코드를 만들어야 합니다. 무조건 1, 2, 3만 붙여서 바코드를 만들었다면 쉬웠겠지만, 아쉽게도 바코드를 만드는 데에 조건이 걸려 있습니다. 바코드에서 인접한 두 개의 부분 수열이 동일하다면 제작할 수 없다고 할 때, 주어진 길이 len의 바코드 중 가장 작은 수를 반환하는 함수를 작성하세요.

만들 수 없는 바코드	만들 수 있는 바코드
11	1312
1231312	3
232312	231213

출력

String 타입을 리턴해야 합니다.
예시로, 121도, 123도 전부 바코드로 제작할 수 있지만 제일 작은 수는 121이기 때문에 121을 반환해야 합니다.

입출력 예시

let output = barcode(3);
console.log(output); // "121"

output = barcode(7);
console.log(output); // "1213121"

output = barcode(20);
console.log(output); // "12131231321231213123"

🤔 나의 생각

부분수열은 몇가지 규칙이 있었다.
뒤에서 첫번째 숫자는 뒤에서 두번째 숫자와 달라야 한다.
뒤에서 첫번째, 두번째 숫자는 뒤에서 세번째, 네번째 숫자와 달라야한다.
위 조건을 n의 길이만큼 탐색한다. 그러나 부분순열이기 때문에 n의 반만큼만 탐색해도 답을 구할 수 있다.
먼저 위 조건을 만족하는 함수를 만들어주어야 한다.
그리고 dfs 함수를 구현해서 위 조건을 만족하면, dfs 조건에 맞을 때 비로소 반환하게 만든다.

code

function barcode(len) {

    // dfs 함수 구현
    const dfs = (str) => {
        if (str.length === len) {
            return str;
        }
        for (let i = 0; i < str.length; i++) {
            // 체크
            if (check(str + i)) {
                // 재귀
                const recursive = dfs(str + i);
                if (recursive) {
                    return recursive;
                }
            }
        }
        return 0;
    }
    // 재귀
    return dfs("");
}

// 부분 수열 체크 함수
function check (str) {
    let reversed = str.split("").reverse().join("");

    for (let [i, len] = [1, parseInt(str.length/2); i <= len; i++]) {
        if (reversed.slice(0, i) === reversed.slice(i, i+i)) {
            return false;
        }
    }
    return true;
}

🙌 느낀점

바코드 문제는 생각보다 정말 어려웠다. 프로그래머스 2단계는 생각보다 쉬웠다. 이번 스프린트는 정말 내 페어분뿐만 아니라 대부분 수강생분들이 다 고통스러워 한다는 것을 느꼈다.

알고리즘을 정말 왜 해야하나 싶을 정도로 나를 고통스럽게 하지만, 또 생각해보면 프로그래밍을 하는데 기본적인 알고리즘 지식이 없는 것도 말이 안된다고 생각한다. 그냥… 다 중요하다. 뭐든 열심히 최선을 다하다보면 언젠간 잘해질꺼라 믿는다.

👊 내일의 TIW(today I Will)

순열, 조합, GCD

← Previous Post Next Post →

Greedy, DFS 알고리즘

📅 TIL #42

🎯 Achievement Goals

👉 프로그래머스 Lv2. 구명보트

문제 설명

제한사항

입출력 예

🤔 나의 생각

code

👉 코플릿 [DFS] 바코드

문제

출력

입출력 예시

🤔 나의 생각

code

🙌 느낀점