221013 :: [프로그래머스] 예상 대진표, 최고의 집합, 야근 지수

예상 대진표

👾 문제 설명
△△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N번의 참가자끼리 게임을 진행합니다. 각 게임에서 이긴 사람은 다음 라운드에 진출할 수 있습니다. 이때, 다음 라운드에 진출할 참가자의 번호는 다시 1번부터 N/2번을 차례대로 배정받습니다. 만약 1번↔2번 끼리 겨루는 게임에서 2번이 승리했다면 다음 라운드에서 1번을 부여받고, 3번↔4번에서 겨루는 게임에서 3번이 승리했다면 다음 라운드에서 2번을 부여받게 됩니다. 게임은 최종 한 명이 남을 때까지 진행됩니다.

이때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지 궁금해졌습니다. 게임 참가자 수 N, 참가자 번호 A, 경쟁자 번호 B가 함수 solution의 매개변수로 주어질 때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지 return 하는 solution 함수를 완성해 주세요. 단, A번 참가자와 B번 참가자는 서로 붙게 되기 전까지 항상 이긴다고 가정합니다.

👾 제한 사항

• N : 21 이상 220 이하인 자연수 (2의 지수 승으로 주어지므로 부전승은 발생하지 않습니다.)
• A, B : N 이하인 자연수 (단, A ≠ B 입니다.)

 

👾 나의 답안

function solution(n, a, b) {
    let count = 0;

    while (true) {
        a = Math.ceil(a / 2);
        b = Math.ceil(b / 2);
        count++;

        if (a == b) {
            break;
        }
    }
    return count;
}

 

• a와 b 각각 2로 나눈 값을 반올림했을 때 같으면 만나게 된다.
• while문을 통해 a와 b를 2로 계속 나누고 a와 b가 같을 경우 while문을 빠져 나온다. Math.ceil()을 사용했다. => 소수점 이하를 올림한다.
• +) Math.round(): 소수점 이하 반올림 || Math.floor(): 소수점 이하 내림

 

function solution(n, a, b) {
    let count = 0;

    while (a != b) {
        a = Math.ceil(a / 2);
        b = Math.ceil(b / 2);
        count++;
    }
    return count;
}

 

• while문 조건을 a와 b의 값이 같지 않은 경우로 설정하면 굳이 if문을 쓸 필요가 없다.

 

---

최고의 집합

👾 문제 설명
자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 "집합"으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다.

- 각 원소의 합이 S가 되는 수의 집합
- 위 조건을 만족하면서 각 원소의 곱이 최대가 되는 집합

예를 들어서 자연수 2개로 이루어진 집합 중 합이 9가 되는 집합은 다음과 같이 4개가 있습니다.
{ 1, 8 }, { 2, 7 }, { 3, 6 }, { 4, 5 }
그중 각 원소의 곱이 최대인 { 4, 5 }가 최고의 집합입니다.

집합의 원소의 개수 n과 모든 원소들의 합 s가 매개변수로 주어질 때, 최고의 집합을 return 하는 solution 함수를 완성해주세요.

👾 제한 사항

• 최고의 집합은 오름차순으로 정렬된 1차원 배열(list, vector) 로 return 해주세요.
• 만약 최고의 집합이 존재하지 않는 경우에 크기가 1인 1차원 배열(list, vector) 에 -1 을 채워서 return 해주세요.
• 자연수의 개수 n은 1 이상 10,000 이하의 자연수입니다.
• 모든 원소들의 합 s는 1 이상, 100,000,000 이하의 자연수입니다.

 

👾 나의 답안

function solution(n, s) {
    if (n > s) return [-1];

    const arr = new Array(n).fill(Math.floor(s / n));
    for (let i = 0; i < s - n * Math.floor(s / n); i++) {
        arr[arr.length - 1 - i] += 1;
    }
    return arr;
}

 

• 원소의 곱이 최대가 되려면 최대한 균등하게 원소 값들을 배분해야 한다.
• 원소들의 합 s보다 원소의 개수 n이 큰 경우, 자연수 n개로 집합을 만들 수 없기 때문에 -1을 배열에 담아 리턴한다.
• 배열 arr에 s를 n으로 나눠서 소수점 이하를 내린 값 n개만큼 채우고, for문을 남은 값(아까 소수점 이하 내린 값 회수)만큼 돌면서 배열의 끝에서부터 1씩 더해준다. (오름차순이므로)
• 처음!! 자발적으로 푼 레벨 3 문제였는데 겁먹고 진입한 것치고는 좀 쉬웠음 🙃

 

---

야근 지수

👾 문제 설명
회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도를 최소화하도록 일할 겁니다. Demi가 1시간 동안 작업량 1만큼을 처리할 수 있다고 할 때, 퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해 야근 피로도를 최소화한 값을 리턴하는 함수 solution을 완성해주세요.

👾 제한 사항

• works는 길이 1 이상, 20,000 이하인 배열입니다.
• works의 원소는 50000 이하인 자연수입니다.
• n은 1,000,000 이하인 자연수입니다.

 

이것도 레벨 3인데 렙삼님 제가 감히 쉽다고 해서 죄송해요

그래도 오늘 마침 야근한 지민이랑 카톡도 했고 이래저래 제목이 자극적이라서 풀이 시도함

 

👾 나의 답안

function solution(n, works) {
    if (works.reduce((a, b) => a + b) <= n) return 0;

    let sorted = works.sort((a, b) => b - a);

    while (n) {
        n--;
        sorted[0]--;
        sorted = sorted.sort((a, b) => b - a);
    }
    return sorted.reduce((a, b) => a + Math.pow(b, 2), 0);
}

 

• 첫 답안, 테스트 케이스는 모두 통과했는데 효율성 문제에서 전부 시간 초과가 뜬다.
• 우선 처리해야 할 작업량보다 근무 시간 n이 같거나 크다면 모든 일을 업무 시간 내에 처리할 수 있으므로 피로도가 없다. 따라서 0을 리턴해 주고 시작한다.
• 문제에서 요구하는 것은 피로도의 최소값이므로, 최대한 큰 수를 없애줘야 한다. (제곱하면 짱 커짐!!) 따라서 **배열을 내림차순으로 정렬하고, 앞에서부터 우선적으로 1 차감, 또 다시 정렬하고 끝에서 1 차감** 의 과정을 반복한다. 
• while문에서 효율성 문제가 있었을 것이다. 조건에 n은 백만 이하 자연수라고 적혀 있다.
• 문제 있는 while문을 통해 어쨌든 배열이 하향 평준화 되었으므로, reduce()를 이용해 제곱의 합을 구한다.

 

function solution(n, works) {
    if (works.reduce((a, b) => a + b) <= n) return 0;

    let sorted = works.sort((a, b) => b - a);

    while (n) {
        for (let i = 0; i < sorted.length; i++) {
            if (sorted[i] >= sorted[0]) {
                sorted[i]--;
                n--;
            }
            if (!n) break;
        }
    }
    return sorted.reduce((a, b) => a + Math.pow(b, 2), 0);
}

 

• 구글링 결과 위 코드는 n의 최대값이 백만이고 works의 최대 길이가 2만이므로 최대 이백억의 시간 복잡도가 나오는 구조라고 한다.
• while 안에 for문을 통해 동일한 값을 한 번에 제거하면 정렬을 매 반복마다 해 줄 필요가 없는 것이다.

 

편-안