Algorithm - KaKao Blind Recruitment Problems

이소라·2023년 1월 23일

Algorithm

목록 보기

38/77

Problem : 개인정보 수집 유효기간

고객의 약관 동의를 얻어서 수집된 1~n번으로 분류되는 개인정보 n개가 있습니다. 약관 종류는 여러 가지 있으며 각 약관마다 개인정보 보관 유효기간이 정해져 있습니다. 당신은 각 개인정보가 어떤 약관으로 수집됐는지 알고 있습니다. 수집된 개인정보는 유효기간 전까지만 보관 가능하며, 유효기간이 지났다면 반드시 파기해야 합니다.
- 예를 들어, A라는 약관의 유효기간이 12 달이고, 2021년 1월 5일에 수집된 개인정보가 A약관으로 수집되었다면 해당 개인정보는 2022년 1월 4일까지 보관 가능하며 2022년 1월 5일부터 파기해야 할 개인정보입니다.
당신은 오늘 날짜로 파기해야 할 개인정보 번호들을 구하려 합니다.
모든 달은 28일까지 있다고 가정합니다.
다음은 오늘 날짜가 2022.05.19일 때의 예시입니다.

약관 종류	유효기간
A	6 달
B	12 달
C	3 달

번호	개인정보 수집 일자	약관 종류
1	2021.05.02	A
2	2021.07.01	B
3	2022.02.19	C
4	2022.02.20	C

위 예시 풀이
- 첫 번째 개인정보는 A약관에 의해 2021년 11월 1일까지 보관 가능하며, 유효기간이 지났으므로 파기해야 할 개인정보입니다.
- 두 번째 개인정보는 B약관에 의해 2022년 6월 28일까지 보관 가능하며, 유효기간이 지나지 않았으므로 아직 보관 가능합니다.
- 세 번째 개인정보는 C약관에 의해 2022년 5월 18일까지 보관 가능하며, 유효기간이 지났으므로 파기해야 할 개인정보입니다.
- 네 번째 개인정보는 C약관에 의해 2022년 5월 19일까지 보관 가능하며, 유효기간이 지나지 않았으므로 아직 보관 가능합니다.
- 따라서 파기해야 할 개인정보 번호는 [1, 3]입니다.
오늘 날짜를 의미하는 문자열 today, 약관의 유효기간을 담은 1차원 문자열 배열 terms와 수집된 개인정보의 정보를 담은 1차원 문자열 배열 privacies가 매개변수로 주어집니다. 이때 파기해야 할 개인정보의 번호를 오름차순으로 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해 주세요.
제한사항
- today는 "YYYY.MM.DD" 형태로 오늘 날짜를 나타냅니다.
- 1 ≤ terms의 길이 ≤ 20
  - terms의 원소는 "약관 종류 유효기간" 형태의 약관 종류와 유효기간을 공백 하나로 구분한 문자열입니다.
  - 약관 종류는 A~Z중 알파벳 대문자 하나이며, terms 배열에서 약관 종류는 중복되지 않습니다.
  - 유효기간은 개인정보를 보관할 수 있는 달 수를 나타내는 정수이며, 1 이상 100 이하입니다.
- 1 ≤ privacies의 길이 ≤ 100
  - privacies[i]는 i+1번 개인정보의 수집 일자와 약관 종류를 나타냅니다.
  - privacies의 원소는 "날짜 약관 종류" 형태의 날짜와 약관 종류를 공백 하나로 구분한 문자열입니다.
  - 날짜는 "YYYY.MM.DD" 형태의 개인정보가 수집된 날짜를 나타내며, today 이전의 날짜만 주어집니다.
  - privacies의 약관 종류는 항상 terms에 나타난 약관 종류만 주어집니다.
- today와 privacies에 등장하는 날짜의 YYYY는 연도,
- MM은 월, DD는 일을 나타내며 점(.) 하나로 구분되어 있습니다.
  - 2000 ≤ YYYY ≤ 2022
  - 1 ≤ MM ≤ 12
  - MM이 한 자릿수인 경우 앞에 0이 붙습니다.
  - 1 ≤ DD ≤ 28
  - DD가 한 자릿수인 경우 앞에 0이 붙습니다.
- 파기해야 할 개인정보가 하나 이상 존재하는 입력만 주어집니다.

Solution

function solution(today, terms, privacies) {
    let answer = [];
  
    const calculateTotalDay = (year, month, day) => {
        const totalDay = day + month * 28 + year * 12 * 28;
        return totalDay;
    }
    
    const calculateDueDay = (date, termMonth) => {
        let [year, month, day] = date.split('.').map((v) => Number(v));
        month += termMonth;
        if (month > 12) {
            month -= 12;
            year += 1;
        }
        const dueDay = calculateTotalDay(year, month, day);
        return dueDay;
    }
    
    const [tYear, tMonth, tDay] = today.split('.').map((v) => Number(v));
    const todayTotalDay = calculateTotalDay(tYear, tMonth, tDay);
    
    const termMap = new Map();
    terms.forEach((term) => {
       const [termName, termMonth] = term.split(' ');
        termMap.set(termName, Number(termMonth));
    });
    
    privacies.forEach((privacy, index) => {
        const [pDate, pTerm] = privacy.split(' ');
        const dueDay = calculateDueDay(pDate, termMap.get(pTerm));
        if (todayTotalDay >= dueDay) {
            answer.push(index + 1);
        }
    });
    return answer;
}

Problem : 택배 배달과 수거하기

당신은 일렬로 나열된 n개의 집에 택배를 배달하려 합니다. 배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하며, 배달을 다니면서 빈 재활용 택배 상자들을 수거하려 합니다.
배달할 택배들은 모두 재활용 택배 상자에 담겨서 물류창고에 보관되어 있고, i번째 집은 물류창고에서 거리 i만큼 떨어져 있습니다. 또한 i번째 집은 j번째 집과 거리 j - i만큼 떨어져 있습니다. (1 ≤ i ≤ j ≤ n)
트럭에는 재활용 택배 상자를 최대 cap개 실을 수 있습니다. 트럭은 배달할 재활용 택배 상자들을 실어 물류창고에서 출발해 각 집에 배달하면서, 빈 재활용 택배 상자들을 수거해 물류창고에 내립니다. 각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 상자의 개수를 알고 있을 때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구하려 합니다. 각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다.
다음은 cap=4 일 때, 최소 거리로 이동하면서 5개의 집에 배달 및 수거하는 과정을 나타낸 예시입니다.
배달 및 수거할 재활용 택배 상자 개수

	집#1	집#2	집#3	집#4	집#5
배달	1개	0개	3개	1개	2개
수거	0개	3개	0개	4개	0개

배달 및 수거 과정

	집#1	집 #2	집 #3	집#4	집#5	설명
남은 배달/수거	1/0	0/3	3/0	1/4	2/0	물류창고에서 택배 3개를 트럭에 실어 출발합니다.
남은 배달/수거	1/0	0/3	3/0	0/4	0/0	물류창고에서 5번째 집까지 이동하면서(거리 5) 4번째 집에 택배 1개를 배달하고, 5번째 집에 택배 2개를 배달합니다.
남은 배달/수거	1/0	0/3	3/0	0/0	0/0	5번째 집에서 물류창고까지 이동하면서(거리 5) 4번째 집에서 빈 택배 상자 4개를 수거한 후, 수거한 빈 택배 상자를 물류창고에 내리고 택배 4개를 트럭에 싣습니다.
남은 배달/수거	0/0	0/3	0/0	0/0	0/0	물류창고에서 3번째 집까지 이동하면서(거리 3) 1번째 집에 택배 1개를 배달하고, 3번째 집에 택배 3개를 배달합니다.
남은 배달/수거	0/0	0/0	0/0	0/0	0/0	3번째 집에서 물류창고까지 이동하면서(거리 3) 2번째 집에서 빈 택배 상자 3개를 수거한 후, 수거한 빈 택배 상자를 물류창고에 내립니다.

16(=5+5+3+3)의 거리를 이동하면서 모든 배달 및 수거를 마쳤습니다. 같은 거리로 모든 배달 및 수거를 마치는 다른 방법이 있지만, 이보다 짧은 거리로 모든 배달 및 수거를 마치는 방법은 없습니다.
트럭에 실을 수 있는 재활용 택배 상자의 최대 개수를 나타내는 정수 cap, 배달할 집의 개수를 나타내는 정수 n, 각 집에 배달할 재활용 택배 상자의 개수를 담은 1차원 정수 배열 deliveries와 각 집에서 수거할 빈 재활용 택배 상자의 개수를 담은 1차원 정수 배열 pickups가 매개변수로 주어집니다. 이때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 return 하도록 solution 함수를 완성해 주세요.
제한사항
- 1 ≤ cap ≤ 50
- 1 ≤ n ≤ 100,000
- deliveries의 길이 = pickups의 길이 = n
- deliveries[i]는 i+1번째 집에 배달할 재활용 택배 상자의 개수를 나타냅니다.
- pickups[i]는 i+1번째 집에서 수거할 빈 재활용 택배 상자의 개수를 나타냅니다.
- 0 ≤ deliveries의 원소 ≤ 50
- 0 ≤ pickups의 원소 ≤ 50
- 트럭의 초기 위치는 물류창고입니다.

Solution

function solution(cap, n, deliveries, pickups) {
    let answer = 0;
    let deliveryBox = 0;
    let pickupBox = 0;
    
    for (let i = n - 1; i >= 0; i--) {
        if (deliveries[i] != 0 || pickups[i] != 0) {
            let count = 0;
            while (deliveryBox < deliveries[i] || pickupBox < pickups[i]) {
                deliveryBox += cap;
                pickupBox += cap;
                count++;
            }
            deliveryBox -= deliveries[i];
            pickupBox -= pickups[i];
            answer += (i + 1) * count * 2;
        }
    }
    return answer;
}

입출력 예
- 입력 : cap = 4, n = 5, deliveries = [1, 0, 3, 1, 2], pickups = [0, 3, 0, 4, 0]
- 출력 : 16
콘솔 출력 예

i번째, deliveries[i], pickups[i], deliveryBox, pickupBox
4 2 0 2 4
// deliveryBox = 4 - 2 = 2, pickupBox = 4 - 0 = 4
answer 10
// while roop count = 1, answer = 0 + (4 + 1) * 1 * 2 = 10

3 1 4 1 0
// deliveryBox = 2 - 1 = 1, pickupBox = 4 - 4 = 0
answer 10
// while roop count = 0, answer = 10 + 0 = 10;

2 3 0 2 4
// deliveryBox = 1 + 4 - 3 = 2, pickupBox = 4 - 0 = 4
answer 16
// while roop count = 1, answer = 10 + (2 + 1) * 1 * 2 = 16

1 0 3 2 1
// deliveryBox = 2 - 0 = 2, pickupBox = 4 - 3 = 1
answer 16
// while roop count = 0, answer = 16 + 0 = 16

0 1 0 1 1
// deliveryBox = 2 - 1 = 1, pickupBox = 1 - 0 = 1
answer 16
// while roop count = 0, answer = 16 + 0 = 16
// result = 16

Problem : 미로 탈출 명령어

n x m 격자 미로가 주어집니다. 당신은 미로의 (x, y)에서 출발해 (r, c)로 이동해서 탈출해야 합니다.
단, 미로를 탈출하는 조건이 세 가지 있습니다.
1. 격자의 바깥으로는 나갈 수 없습니다.
2. (x, y)에서 (r, c)까지 이동하는 거리가 총 k여야 합니다.
  - 이때, (x, y)와 (r, c)격자를 포함해, 같은 격자를 두 번 이상 방문해도 됩니다.
3. 미로에서 탈출한 경로를 문자열로 나타냈을 때, 문자열이 사전 순으로 가장 빠른 경로로 탈출해야 합니다.
이동 경로는 다음과 같이 문자열로 바꿀 수 있습니다.
- l: 왼쪽으로 한 칸 이동
- r: 오른쪽으로 한 칸 이동
- u: 위쪽으로 한 칸 이동
- d: 아래쪽으로 한 칸 이동
- 예를 들어, 왼쪽으로 한 칸, 위로 한 칸, 왼쪽으로 한 칸 움직였다면, 문자열 "lul"로 나타낼 수 있습니다.
미로에서는 인접한 상, 하, 좌, 우 격자로 한 칸씩 이동할 수 있습니다.
예를 들어 다음과 같이 3 x 4 격자가 있다고 가정해 보겠습니다.

....
..S.
E...

미로의 좌측 상단은 (1, 1)이고 우측 하단은 (3, 4)입니다. .은 빈 공간, S는 출발 지점, E는 탈출 지점입니다.
탈출까지 이동해야 하는 거리 k가 5라면 다음과 같은 경로로 탈출할 수 있습니다.
1. lldud
2. ulldd
3. rdlll
4. dllrl
5. dllud
6. ...
이때 dllrl보다 사전 순으로 빠른 경로로 탈출할 수는 없습니다.
격자의 크기를 뜻하는 정수 n, m, 출발 위치를 뜻하는 정수 x, y, 탈출 지점을 뜻하는 정수 r, c, 탈출까지 이동해야 하는 거리를 뜻하는 정수 k가 매개변수로 주어집니다.
이때, 미로를 탈출하기 위한 경로를 return 하도록 solution 함수를 완성해주세요.
- 단, 위 조건대로 미로를 탈출할 수 없는 경우 "impossible"을 return 해야 합니다.
제한사항
- 2 ≤ n (= 미로의 세로 길이) ≤ 50
- 2 ≤ m (= 미로의 가로 길이) ≤ 50
- 1 ≤ x ≤ n
- 1 ≤ y ≤ m
- 1 ≤ r ≤ n
- 1 ≤ c ≤ m
- (x, y) ≠ (r, c)
- 1 ≤ k ≤ 2,500

Solution

테스트케이스는 통과했지만, 시간초과된 코드

function solution(n, m, x, y, r, c, k) {
    let answer = '';
    const paths = [];
    const movementObj = {
        l: [0, -1],
        r: [0, 1],
        u: [-1, 0],
        d: [1, 0],
    };
    
    const dfs = (prevX, prevY, distance, prevPath) => {
        if (distance > k) {
            return;
        }
        if (distance === k && prevX === r && prevY === c) {
            paths.push(prevPath);
            return;
        }
        for (const [movement, position] of Object.entries(movementObj)) {
            const positionX = prevX + position[0];
            const positionY = prevY + position[1];
            const path = prevPath + movement;
            if (positionX < 1 ||positionX > n || positionY < 1 || positionY > m) {
                continue;
            }
            dfs(positionX, positionY, distance + 1, path);
        }  
    };
    dfs(x, y, 0, '');
    paths.sort();
    return paths[0] || 'impossible';
}

다른 사람 풀이를 참조한 코드 (참고 : 2023 KAKAO BLIND RECRUITMENT - 미로 탈출 명령어)

function solution(n, m, x, y, r, c, k) {
    let answer = 'impossible';
    const stack = [[x, y, '']];
    
    while (stack.length) {
        const [positionX, positionY, path] = stack.pop();
        
        if (path.length === k && positionX === r && positionY === c) {
            answer = path;
            break;
        }
        
        const remain = k - path.length;
        const shortestPath = Math.abs(positionX - r) + Math.abs(positionY - c);
        
        if (remain < shortestPath || remain % 2 !== shortestPath % 2) {
            continue;
        }
        
        if (positionX > 1) {
            stack.push([positionX - 1, positionY, path + 'u']);
        }
        if (positionY < m) {
            stack.push([positionX, positionY + 1, path + 'r']);
        }
        if (positionY > 1) {
            stack.push([positionX, positionY -1, path + 'l']);
        }
        if (positionX < n) {
            stack.push([positionX + 1, positionY, path + 'd']);
        }
    }
    return answer;
}

콘솔 출력 예

// stack
// path, positionX, positionY, remain, shortestPath

// 초기값
stack [ [ 2, 3, '' ] ]
'' 2 3 5 3
// 1 < positionX < n, 1 < positionY < m 이므로 ''에 u, r, l, d를 붙임
stack [ [ 1, 3, 'u' ], [ 2, 4, 'r' ], [ 2, 2, 'l' ], [ 3, 3, 'd' ] ]
d 3 3 4 2
// 1 < positionX, 1 < positionY < m 이므로 'd'에 u, r, l를 붙임
stack [
  [ 1, 3, 'u' ],
  [ 2, 4, 'r' ],
  [ 2, 2, 'l' ],
  [ 2, 3, 'du' ],
  [ 3, 4, 'dr' ],
  [ 3, 2, 'dl' ]
]
dl 3 2 3 1
// 1 < positionX, 1 < positionY < m 이므로 'dl'에 u, r, l를 붙임
stack [
  [ 1, 3, 'u' ],
  [ 2, 4, 'r' ],
  [ 2, 2, 'l' ],
  [ 2, 3, 'du' ],
  [ 3, 4, 'dr' ],
  [ 2, 2, 'dlu' ],
  [ 3, 3, 'dlr' ],
  [ 3, 1, 'dll' ]
]
dll 3 1 2 0
// 1 < positionX, positionY < m 이므로 'dll'에 u, r를 붙임
stack [
  [ 1, 3, 'u' ],
  [ 2, 4, 'r' ],
  [ 2, 2, 'l' ],
  [ 2, 3, 'du' ],
  [ 3, 4, 'dr' ],
  [ 2, 2, 'dlu' ],
  [ 3, 3, 'dlr' ],
  [ 2, 1, 'dllu' ],
  [ 3, 2, 'dllr' ]
]
dllr 3 2 1 1
// 1 < positionX, 1 < positionY < m 이므로 'dll'에 u, r, l를 붙임
stack [
  [ 1, 3, 'u' ],
  [ 2, 4, 'r' ],
  [ 2, 2, 'l' ],
  [ 2, 3, 'du' ],
  [ 3, 4, 'dr' ],
  [ 2, 2, 'dlu' ],
  [ 3, 3, 'dlr' ],
  [ 2, 1, 'dllu' ],
  [ 2, 2, 'dllru' ],
  [ 3, 3, 'dllrr' ],
  [ 3, 1, 'dllrl' ]
]
// path.length = 5, positionX = 3, positionY = 1이므로 'dllrl' 반환

Problem : 이모티콘 할인행사

카카오톡에서는 이모티콘을 무제한으로 사용할 수 있는 이모티콘 플러스 서비스 가입자 수를 늘리려고 합니다.
이를 위해 카카오톡에서는 이모티콘 할인 행사를 하는데, 목표는 다음과 같습니다.
1. 이모티콘 플러스 서비스 가입자를 최대한 늘리는 것.
2. 이모티콘 판매액을 최대한 늘리는 것.
1번 목표가 우선이며, 2번 목표가 그 다음입니다.
이모티콘 할인 행사는 다음과 같은 방식으로 진행됩니다.
- n명의 카카오톡 사용자들에게 이모티콘 m개를 할인하여 판매합니다.
- 이모티콘마다 할인율은 다를 수 있으며, 할인율은 10%, 20%, 30%, 40% 중 하나로 설정됩니다.
카카오톡 사용자들은 다음과 같은 기준을 따라 이모티콘을 사거나, 이모티콘 플러스 서비스에 가입합니다.
- 각 사용자들은 자신의 기준에 따라 일정 비율 이상 할인하는 이모티콘을 모두 구매합니다.
- 각 사용자들은 자신의 기준에 따라 이모티콘 구매 비용의 합이 일정 가격 이상이 된다면, 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입합니다.
다음은 2명의 카카오톡 사용자와 2개의 이모티콘이 있을때의 예시입니다.

사용자	비율	가격
1	40	10,000
2	25	10,000

이모티콘	가격
1	7,000
2	9,000

1번 사용자는 40%이상 할인하는 이모티콘을 모두 구매하고, 이모티콘 구매 비용이 10,000원 이상이 되면 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입합니다.
2번 사용자는 25%이상 할인하는 이모티콘을 모두 구매하고, 이모티콘 구매 비용이 10,000원 이상이 되면 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입합니다.
1번 이모티콘의 가격은 7,000원, 2번 이모티콘의 가격은 9,000원입니다.
만약, 2개의 이모티콘을 모두 40%씩 할인한다면, 1번 사용자와 2번 사용자 모두 1,2번 이모티콘을 구매하게 되고, 결과는 다음과 같습니다.

사용자	구매한 이모티콘	이모티콘 구매비용	이모티콘 플러스 서비스 가입 여부
1	1, 2	9,600	X
2	1, 2	9,600	X

이모티콘 플러스 서비스 가입자는 0명이 늘어나고 이모티콘 판매액은 19,200원이 늘어납니다.
하지만, 1번 이모티콘을 30% 할인하고 2번 이모티콘을 40% 할인한다면 결과는 다음과 같습니다.

사용자	구매한 이모티콘	이모티콘 구매비용	이모티콘 플러스 서비스 가입 여부
1	2	5,400	X
2	1, 2	10,300	O

2번 사용자는 이모티콘 구매 비용을 10,000원 이상 사용하여 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입하게 됩니다.
따라서, 이모티콘 플러스 서비스 가입자는 1명이 늘어나고 이모티콘 판매액은 5,400원이 늘어나게 됩니다.
카카오톡 사용자 n명의 구매 기준을 담은 2차원 정수 배열 users, 이모티콘 m개의 정가를 담은 1차원 정수 배열 emoticons가 주어집니다. 이때, 행사 목적을 최대한으로 달성했을 때의 이모티콘 플러스 서비스 가입 수와 이모티콘 매출액을 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해주세요.
제한사항
- 1 ≤ users의 길이 = n ≤ 100
- users의 원소는 [비율, 가격]의 형태입니다.
- users[i]는 i+1번 고객의 구매 기준을 의미합니다.
- 비율% 이상의 할인이 있는 이모티콘을 모두 구매한다는 의미입니다.
  - 1 ≤ 비율 ≤ 40
- 가격이상의 돈을 이모티콘 구매에 사용한다면, 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입한다는 의미입니다.
  - 100 ≤ 가격 ≤ 1,000,000
  - 가격은 100의 배수입니다.
- 1 ≤ emoticons의 길이 = m ≤ 7
  - emoticons[i]는 i+1번 이모티콘의 정가를 의미합니다.
  - 100 ≤ emoticons의 원소 ≤ 1,000,000
  - emoticons의 원소는 100의 배수입니다.

Solution

다른 사람 풀이를 참고한 코드 (참고 : [프로그래머스/JavaScript] Lv.2 이모티콘 할인행사)

function solution(users, emoticons) {
    const answer = [0, 0];
    const saleRates = [10, 20, 30, 40];
    const cases = [];
    
    const dfs = (emoticons, emoticonRatesAndPrices) => {
        if (!emoticons.length) {
            cases.push(emoticonRatesAndPrices);
            return;
        }
        
        for (let i = 0; i < saleRates.length; i++) {
            dfs(emoticons.slice(1), [... emoticonRatesAndPrices, [saleRates[i], emoticons[0]]]);
        }
    }
    
    dfs(emoticons, []);
    
    const getDiscountedPrice = (price, saleRate) => {
        return price * (100 - saleRate) / 100;
    };
    
    cases.forEach((emoticonRatesAndPrices) => {
        let subscriberCount = 0;
        let totalPrice = 0;
        
        users.forEach(([minSaleRate, thresholdPrice]) => {
            let userPrice = 0;
            
            emoticonRatesAndPrices.forEach(([saleRate, emoticonPrice]) => {
               if (saleRate >= minSaleRate) {
                   userPrice += getDiscountedPrice(emoticonPrice, saleRate);
               } 
            });
            
            if (userPrice >= thresholdPrice) {
                subscriberCount++;
            } else {
                totalPrice += userPrice;
            }
        });
        
        if (answer[0] < subscriberCount) {
            answer[0] = subscriberCount;
            answer[1] = totalPrice;
        } else if (answer[0] === subscriberCount && answer[1] < totalPrice) {
            answer[1] = totalPrice;
        }
    });
    return answer;
}

Problem : 표현 가능한 이진트리

당신은 이진트리를 수로 표현하는 것을 좋아합니다.
이진트리를 수로 표현하는 방법은 다음과 같습니다.
1. 이진수를 저장할 빈 문자열을 생성합니다.
2. 주어진 이진트리에 더미 노드를 추가하여 포화 이진트리로 만듭니다.
  - 루트 노드는 그대로 유지합니다.
3. 만들어진 포화 이진트리의 노드들을 가장 왼쪽 노드부터 가장 오른쪽 노드까지, 왼쪽에 있는 순서대로 살펴봅니다
  - 노드의 높이는 살펴보는 순서에 영향을 끼치지 않습니다.
4. 살펴본 노드가 더미 노드라면 문자열 뒤에 0을 추가하고, 더미 노드가 아니라면 문자열 뒤에 1을 추가합니다.
5. 문자열에 저장된 이진수를 십진수로 변환합니다.
이진트리에서 리프 노드가 아닌 노드는 자신의 왼쪽 자식이 루트인 서브트리의 노드들보다 오른쪽에 있으며, 자신의 오른쪽 자식이 루트인 서브트리의 노드들보다 왼쪽에 있다고 가정합니다.
다음은 이진트리를 수로 표현하는 예시입니다.
- 주어진 이진트리는 다음과 같습니다.

주어진 이진트리에 더미노드를 추가하여 포화 이진트리로 만들면 다음과 같습니다.
- 더미 노드는 점선으로 표시하였고, 노드 안의 수는 살펴보는 순서를 의미합니다.

노드들을 왼쪽에 있는 순서대로 살펴보며 0과 1을 생성한 문자열에 추가하면 "0111010"이 됩니다. 이 이진수를 십진수로 변환하면 58입니다.
이진트리로 만들고 싶은 수를 담은 1차원 정수 배열 numbers가 주어집니다.
numbers에 주어진 순서대로 하나의 이진트리로 해당 수를 표현할 수 있다면 1을, 표현할 수 없다면 0을 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해주세요.
제한사항
- 1 ≤ numbers의 길이 ≤ 10,000
- 1 ≤ numbers의 원소 ≤ 1015

Solution

function solution(numbers) {
    const binaryNumbers = numbers.map((num) => num.toString(2));
    let result;
    
    const calculateHeight = (num, height) => {
        if (num < 2) {
            return height;
        }
        const quotient = Math.floor(num / 2);
        height += 1;
        
        return calculateHeight(quotient, height); 
    }
    
    const makeFullBinaryTree = (numStr) => {
        const height = calculateHeight(numStr.length, 0);
        if (numStr.length === 2 ** height - 1) {
            return numStr;
        }
        const dummyNodeCount = 2 ** (height + 1) - 1 - numStr.length;
        const str = '0'.repeat(dummyNodeCount) + numStr;
        return str;
    }
    
    const checkRootValid = (numStr) => {
        let rootIndex = Math.floor(numStr.length / 2);
        
        if (numStr.length % 2 === 0) {
            rootIndex -= 1;
        }
        if (numStr[rootIndex] !== '1') {
            result = 0;
            return false;
        }
        return true;
    };
    
    const chechChildrenValid = (numStr, startIndex, endIndex, isDummy) => {
        const midIndex = Math.floor((startIndex + endIndex) / 2);
        const curNode = Number(numStr[midIndex]);
        
        if (isDummy && curNode) {
            result = 0;
            return false;
        }
        if (startIndex < endIndex) {
            chechChildrenValid(numStr, startIndex, midIndex - 1, !curNode);
            chechChildrenValid(numStr, midIndex + 1, endIndex, !curNode);
        }
        return true;
    };
    
    const checkBinaryTreeValid = (numStr) => {
        if (!checkRootValid(numStr)) {
            return false;
        }
        if (!chechChildrenValid(numStr, 0, numStr.length - 1, false)) {
            return false;
        }
        return true;
    };
    
    const answer = binaryNumbers.map((numStr) => {
        result = 1;
        const fullBinaryTreeStr = makeFullBinaryTree(numStr);
        checkBinaryTreeValid(fullBinaryTreeStr);
        return result;
    });
    return answer;
}

문제 풀이 (참고: 문제에 대한 간단한 해설, [프로그래머스] 표현 가능한 이진트리)
1. toString 메서드를 사용하여 numbers의 십진수를 이진수로 변환하기
2. 포화 이진 트리(Full Binary Tree) 만들기
  - 포화 이진 트리 : 부모 트리에 자식 트리가 항상 2개 있고, 높이를 맞춘 트리
  - 포화 이진 트리의 노드 갯수 : 2^(높이) - 1
  - 이진수의 길이를 재귀적으로 2로 나눠서 높이를 계산함
  - 이진수의 길이와 포화 이진 트리의 노드 갯수를 비교하여 차이가 나면, 부족한 갯수만큼 앞에 '0'을 붙여줌
3. 이진수를 유효한 이진트리로 표현할 수 있는지 판별하기
  - 루트 노드가 0인지 확인하기
    - 이진수의 길이가 홀수이면, 루트노드의 인덱스는 전체 길이의 절반임
    - 이진수의 길이가 짝수이면, 루트노드의 인덱스는 전체 길이의 절반 - 1가 됨
    - 루트 노드가 0일 경우, result에 0을 대입하고 false를 return함
  - Binary Search를 사용하여 이진 트리를 탐색함
    - 부모노드가 0이고 자식노드가 1인 경우, result가 0을 대입하고 false를 return함
    - startIndex가 endIndex보다 작은 경우에만 이진 트리를 탐색하는 함수를 재귀적으로 호출함
    - 모든 경우를 통과할 경우, result는 1 그대로이고 true를 return함