Algorithm - Kakao Previous Problems

이소라·2022년 11월 21일
0

Algorithm

목록 보기
31/77
post-custom-banner

Problem: 주차 요금 계산

  • 주차장의 요금표와 차량이 들어오고(입차) 나간(출차) 기록이 주어졌을 때, 차량별로 주차 요금을 계산하려고 합니다. 아래는 하나의 예시를 나타냅니다.

  • 요금표

기본 시간(분)기본 요금(원)단위 시간(분)단위 요금(원)
180500010600
  • 입/출차 기록
시간(시:분)차량 번호내역
05:345961입차
06:000000입차
06:340000출차
07:595961출차
07:590148입차
18:590000입차
19:090148출차
22:595961입차
23:005961출차

  • 자동차 주차별 주차 요금

    • 차량 번호 : 0000
      • 누적 주차 시간(분) : 34 + 300 = 334
      • 주차 요금(원) : 5000 + ⌈(334 - 180) / 10⌉ x 600 = 14600
    • 차량 번호 : 0148
      • 누적 주차 시간(분) : 670
      • 주차 요금(원) : 5000 +⌈(670 - 180) / 10⌉x 600 = 34400
    • 차량 번호 : 0000
      • 누적 주차 시간(분) : 145 + 1 = 146
      • 주차 요금(원) : 5000

  • 어떤 차량이 입차된 후에 출차된 내역이 없다면, 23:59에 출차된 것으로 간주합니다.

    • 0000번 차량은 18:59에 입차된 이후, 출차된 내역이 없습니다. 따라서, 23:59에 출차된 것으로 간주합니다.

  • 00:00부터 23:59까지의 입/출차 내역을 바탕으로 차량별 누적 주차 시간을 계산하여 요금을 일괄로 정산합니다.

  • 누적 주차 시간이 기본 시간이하라면, 기본 요금을 청구합니다.

  • 누적 주차 시간이 기본 시간을 초과하면, 기본 요금에 더해서, 초과한 시간에 대해서 단위 시간 마다 단위 요금을 청구합니다.

    • 초과한 시간이 단위 시간으로 나누어 떨어지지 않으면, 올림합니다.
    • ⌈a⌉ : a보다 작지 않은 최소의 정수를 의미합니다. 즉, 올림을 의미합니다.

  • 주차 요금을 나타내는 정수 배열 fees, 자동차의 입/출차 내역을 나타내는 문자열 배열 records가 매개변수로 주어집니다. 차량 번호가 작은 자동차부터 청구할 주차 요금을 차례대로 정수 배열에 담아서 return 하도록 solution 함수를 완성해주세요.

  • 제한사항

    • fee의 길이 = 4
      • fees[0] = 기본 시간(분)
      • 1 ≤ fees[0] ≤ 1,439
      • fees[1] = 기본 요금(원)
      • 0 ≤ fees[1] ≤ 100,000
      • fees[2] = 단위 시간(분)
      • 1 ≤ fees[2] ≤ 1,439
      • fees[3] = 단위 요금(원)
      • 1 ≤ fees[3] ≤ 10,000
    • 1 ≤ records의 길이 ≤ 1,000
      • records의 각 원소는 "시각 차량번호 내역" 형식의 문자열입니다.
      • 시각, 차량번호, 내역은 하나의 공백으로 구분되어 있습니다.
      • 시각은 차량이 입차되거나 출차된 시각을 나타내며, HH:MM 형식의 길이 5인 문자열입니다.
        • HH:MM은 00:00부터 23:59까지 주어집니다.
        • 잘못된 시각("25:22", "09:65" 등)은 입력으로 주어지지 않습니다.
      • 차량번호는 자동차를 구분하기 위한, '0'~'9'로 구성된 길이 4인 문자열입니다.
      • 내역은 길이 2 또는 3인 문자열로, IN 또는 OUT입니다. IN은 입차를, OUT은 출차를 의미합니다.
      • records의 원소들은 시각을 기준으로 오름차순으로 정렬되어 주어집니다.
      • records는 하루 동안의 입/출차된 기록만 담고 있으며, 입차된 차량이 다음날 출차되는 경우는 입력으로 주어지지 않습니다.
      • 같은 시각에, 같은 차량번호의 내역이 2번 이상 나타내지 않습니다.
      • 마지막 시각(23:59)에 입차되는 경우는 입력으로 주어지지 않습니다.
      • 아래의 예를 포함하여, 잘못된 입력은 주어지지 않습니다.
        • 주차장에 없는 차량이 출차되는 경우
        • 주차장에 이미 있는 차량(차량번호가 같은 차량)이 다시 입차되는 경우

Solution

function solution(fees, records) {
    let answer = [];
    const carRecords = new Map();
    const parkingTimes = new Map();
    
    const getParkingTime = function(inTime, outTime) {
        let [inHour, inMinute] = inTime.split(':').map((time) => +time);
        let [outHour, outMinute] = outTime.split(':').map((time) => +time);
        const totalInTime = inHour * 60 + inMinute;
        const totalOutTime = outHour * 60 + outMinute;
        const parkingTime = totalOutTime - totalInTime;
        return parkingTime;
    }
    
    records.forEach((record) => {
        const [time, car, sign] = record.split(' ');
        const timeLog = carRecords.get(car);
        
        if (timeLog) {
            const parkingTime = getParkingTime(timeLog, time);
            const parkLog = parkingTimes.get(car);
            parkLog ? parkingTimes.set(car, parkLog + parkingTime) : parkingTimes.set(car, parkingTime);
            carRecords.set(car, null);
        } else {
            carRecords.set(car, time);
        }
        
    });
    
    for (const [car, time] of carRecords.entries()) {
        if (time == null) continue;
        const parkingTime = getParkingTime(time, "23:59");
        const parkingLog = parkingTimes.get(car);
        parkingLog ? parkingTimes.set(car, parkingLog + parkingTime) : parkingTimes.set(car, parkingTime);
    }
    
    const [baseTime, baseFee, unitTime, unitFee] = fees;
    
    const timeArr = Array.from(parkingTimes.keys()).sort((a, b) => a - b);
    
    timeArr.forEach((car) => {
        const time = parkingTimes.get(car);
        if (time <= baseTime) {
            answer.push(baseFee);
            return;
        }
        const overTime = Math.ceil((time - baseTime) / unitTime);
        const totalFee = baseFee + overTime * unitFee;
        
        answer.push(totalFee);
    })
    
    
    return answer;
}

Problem: 거리두기 확인하기

  • 개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다.

  • 코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼, 아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다.

    1. 대기실은 5개이며, 각 대기실은 5x5 크기입니다.
    2. 거리두기를 위하여 응시자들 끼리는 맨해튼 거리가 2 이하로 앉지 말아 주세요.
      • T1(r1, c1), T2(r2, c2) 사이의 맨해튼 거리 = |r1 - r2| + |c1 - c2|
    3. 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다.

  • 5개의 대기실을 본 죠르디는 각 대기실에서 응시자들이 거리두기를 잘 기키고 있는지 알고 싶어졌습니다. 자리에 앉아있는 응시자들의 정보와 대기실 구조를 대기실별로 담은 2차원 문자열 배열 places가 매개변수로 주어집니다. 각 대기실별로 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

  • 제한사항

    • places의 행 길이(대기실 개수) = 5
      • places의 각 행은 하나의 대기실 구조를 나타냅니다.
    • places의 열 길이(대기실 세로 길이) = 5
    • places의 원소는 P,O,X로 이루어진 문자열입니다.
      • places 원소의 길이(대기실 가로 길이) = 5
      • P는 응시자가 앉아있는 자리를 의미합니다.
      • O는 빈 테이블을 의미합니다.
      • X는 파티션을 의미합니다.
    • return 값 형식
      • 1차원 정수 배열에 5개의 원소를 담아서 return 합니다.
        • places에 담겨 있는 5개 대기실의 순서대로, 거리두기 준수 여부를 차례대로 배열에 담습니다.
        • 각 대기실 별로 모든 응시자가 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 담습니다.

  • 입출력 예

    • 입력 : [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]]
    • 출력 : [1, 0, 1, 1, 1]

  • 첫 번째 대기실

    • 모든 응시자가 거리두기를 지키고 있습니다
No.01234
0POOOX
1OXXOX
2OPXPX
3OOXOX
4POXXP
  • 두 번째 대기실
    • (0,0) 자리 응시자와 (2,0) 자리 응사자가 거리두기를 지키고 있지 않습니다.
    • (1, 2) 자리의 응시자와 (0, 3) 자리의 응시자가 거리두기를 지키고 있지 않습니다.
    • (4, 3) 자리의 응시자와 (4, 4) 자리의 응시자가 거리두기를 지키고 있지 않습니다.
No.01234
0POOPX
1OXPXP
2PXXXO
3OXXXO
4OOOPP
  • 세 번째 대기실
    • 모든 응시자가 거리두기를 지키고 있습니다
No.01234
0PXOPX
1OXOXP
2OXPOX
3OXXOP
4PXPOX
  • 네 번째 대기실
    • 대기실에 응시자가 없으므로 거리두기를 지키고 있습니다.
No.01234
0OOOXX
1XOOOX
2OOOXX
3OXOOX
4OOOOO
  • 다섯 번째 대기실
    • 모든 응시자가 거리두기를 지키고 있습니다
No.01234
0PXPXP
1XPXPX
2PXPXP
3XPXPX
4PXPXP
  • 두 번째 대기실을 제외한 모든 대기실에서 거리두기가 지켜지고 있으므로, 배열 [1, 0, 1, 1, 1]을 return 합니다.

Solution

function solution(places) {
    let answer = [];
    const size = 5;
    const dx = [-1, 0, 1, 0];
    const dy = [0, 1, 0, -1];
    
    function isOutBoundary(x, y) {
        return x < 0 || x >= size || y < 0 || y >= size;
    }
    
    function checkDistance(place) {
        let placeArr = place.map((row) => row.split(''));
        let queue = [];
        
        for (let i = 0; i < size; i++) {
            for (let j = 0; j < size; j++) {
                if (placeArr[i][j] === 'P') {
                    queue.push([i, j]);
                }
            }
        }
        
        while (queue.length) {
            const [x, y] = queue.shift();
            
            for (let i = 0; i < size - 1; i++) {
                let nx1 = x + dx[i];
                let ny1 = y + dy[i];
                
                if (isOutBoundary(nx1, ny1)) continue;
                if (placeArr[nx1][ny1] === 'X') continue;
                if (placeArr[nx1][ny1] === 'P') return 0;
                
                for (let j = 0; j < size - 1; j++) {
                    let nx2 = nx1 + dx[j];
                    let ny2 = ny1 + dy[j];
                    
                    if (isOutBoundary(nx2, ny2)) continue;
                    if (nx2 === x && ny2 === y) continue;
                    if (placeArr[nx2][ny2] === 'P') return 0;
                }
                
            }
        }
        
        return 1;
    }
    
    places.forEach((place) => {
        answer.push(checkDistance(place));
    });
    
    return answer;
}
  • 풀이
    1. 응시자 P를 기준으로 상하좌우로 2번 움직였을 때, 응시자 P가 있으면 거리두기를 지키지 않은 것이다
    2. 1번 움직였을 때, 파티션 X인지 빈 테이블 O인지 응시자 P인지 판단함
      • 파티션 X의 경우, 넘어감
      • 응시자 P의 경우, 거리두기를 지키지 않았으므로 0을 반환함
      • 빈테이블 O의 경우, 1번 더 움직여서 위의 2번 과정을 반복함
      • 모든 경우를 만족하면 1을 반환함

Problem: 키패드 누르기

  • 이 전화 키패드에서 왼손과 오른손의 엄지손가락만을 이용해서 숫자만을 입력하려고 합니다.
    맨 처음 왼손 엄지손가락은 * 키패드에 오른손 엄지손가락은 # 키패드 위치에서 시작하며, 엄지손가락을 사용하는 규칙은 다음과 같습니다.
    1. 엄지손가락은 상하좌우 4가지 방향으로만 이동할 수 있으며 키패드 이동 한 칸은 거리로 1에 해당합니다.
    2. 왼쪽 열의 3개의 숫자 1, 4, 7을 입력할 때는 왼손 엄지손가락을 사용합니다.
    3. 오른쪽 열의 3개의 숫자 3, 6, 9를 입력할 때는 오른손 엄지손가락을 사용합니다.
    4. 가운데 열의 4개의 숫자 2, 5, 8, 0을 입력할 때는 두 엄지손가락의 현재 키패드의 위치에서 더 가까운 엄지손가락을 사용합니다.
    4-1. 만약 두 엄지손가락의 거리가 같다면, 오른손잡이는 오른손 엄지손가락, 왼손잡이는 왼손 엄지손가락을 사용합니다.

  • 순서대로 누를 번호가 담긴 배열 numbers, 왼손잡이인지 오른손잡이인 지를 나타내는 문자열 hand가 매개변수로 주어질 때, 각 번호를 누른 엄지손가락이 왼손인 지 오른손인 지를 나타내는 연속된 문자열 형태로 return 하도록 solution 함수를 완성해주세요.

  • 제한사항

    • numbers 배열의 크기는 1 이상 1,000 이하입니다.
    • numbers 배열 원소의 값은 0 이상 9 이하인 정수입니다.
    • hand는 "left" 또는 "right" 입니다.
      • "left"는 왼손잡이, "right"는 오른손잡이를 의미합니다.
    • 왼손 엄지손가락을 사용한 경우는 L, 오른손 엄지손가락을 사용한 경우는 R을 순서대로 이어붙여 문자열 형태로 return 해주세요.

  • 입출력 예
    - 입력 : numbers = [1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5], hand = "right"

    • 출력 : "LRLLLRLLRRL"

  • 입출력 설명

왼손 위치오른손 위치눌러야할 숫자사용한 손설명
*#1L1은 왼손으로 누름
1#3R3은 오른손으로 누름
134L4는 왼손으로 누름
435L왼손 거리는 1, 오른손 거리는 2이므로 왼손으로 5를 누름
538L왼손 거리는 1, 오른손 거리는 3이므로 왼손으로 8을 누름
832R왼손 거리는 2, 오른손 거리는 1이므로 오른손으로 2를 누름
821L1은 왼손으로 누름
124L4는 왼손으로 누름
425R왼손 거리와 오른손 거리가 1로 같으므로, 오른손으로 5를 누름
459R9는 오른손으로 누름
495L왼손 거리는 1, 오른손 거리는 2이므로 왼손으로 5를 누름
59--

Solution

function solution(numbers, hand) {
    let answer = '';
    let left = 10;
    let right = 12;
    const lines = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [10, 11, 12]];
    
    const getDistance = (start, end) => {
        let startLineIndex, startNumIndex, endLineIndex, endNumIndex;
        lines.forEach((line, lineIndex) => {
            line.forEach((num, numIndex) => {
                if (num === start) {
                    startLineIndex = lineIndex;
                    startNumIndex = numIndex;
                }
                if (num === end) {
                    endLineIndex = lineIndex;
                    endNumIndex = numIndex;
                }
            });
        });
        
        const distance = Math.abs(startLineIndex - endLineIndex) + Math.abs(startNumIndex - endNumIndex);
        return distance;
    }
    
    numbers.forEach((num) => {
        const moveLeft = () => {
            answer += 'L';
            left = num;
        }
        const moveRight = () => {
            answer += 'R';
            right = num;
        }
       if (num === 1 || num === 4 || num === 7) {
           return moveLeft();
       } 
       if (num === 3 || num === 6 || num === 9) {
           return moveRight();
       }
        if (num === 2 || num === 5 || num === 8 || num === 0) {
            if (num === 0) {
                num = 11;
            }
            const leftDistance = getDistance(left, num);
            const rightDistance = getDistance(right, num);
            
            if (leftDistance < rightDistance) {
                return moveLeft();
            }
            if (leftDistance > rightDistance) {
                return moveRight();
            } 
            if (leftDistance === rightDistance) {
                return hand === 'left' ? moveLeft() : moveRight();
            }
        }
    });
    return answer;
}

Problem: 양과 늑대

  • 2진 트리 모양 초원의 각 노드에 늑대와 양이 한 마리씩 놓여 있습니다. 이 초원의 루트 노드에서 출발하여 각 노드를 돌아다니며 양을 모으려 합니다. 각 노드를 방문할 때 마다 해당 노드에 있던 양과 늑대가 당신을 따라오게 됩니다. 이때, 늑대는 양을 잡아먹을 기회를 노리고 있으며, 당신이 모은 양의 수보다 늑대의 수가 같거나 더 많아지면 바로 모든 양을 잡아먹어 버립니다. 당신은 중간에 양이 늑대에게 잡아먹히지 않도록 하면서 최대한 많은 수의 양을 모아서 다시 루트 노드로 돌아오려 합니다.

  • 예를 들어, 위 그림의 경우(루트 노드에는 항상 양이 있습니다) 0번 노드(루트 노드)에서 출발하면 양을 한마리 모을 수 있습니다. 다음으로 1번 노드로 이동하면 당신이 모은 양은 두 마리가 됩니다. 이때, 바로 4번 노드로 이동하면 늑대 한 마리가 당신을 따라오게 됩니다. 아직은 양 2마리, 늑대 1마리로 양이 잡아먹히지 않지만, 이후에 갈 수 있는 아직 방문하지 않은 모든 노드(2, 3, 6, 8번)에는 늑대가 있습니다. 이어서 늑대가 있는 노드로 이동한다면(예를 들어 바로 6번 노드로 이동한다면) 양 2마리, 늑대 2마리가 되어 양이 모두 잡아먹힙니다. 여기서는 0번, 1번 노드를 방문하여 양을 2마리 모은 후, 8번 노드로 이동한 후(양 2마리 늑대 1마리) 이어서 7번, 9번 노드를 방문하면 양 4마리 늑대 1마리가 됩니다. 이제 4번, 6번 노드로 이동하면 양 4마리, 늑대 3마리가 되며, 이제 5번 노드로 이동할 수 있게 됩니다. 따라서 양을 최대 5마리 모을 수 있습니다.
  • 각 노드에 있는 양 또는 늑대에 대한 정보가 담긴 배열 info, 2진 트리의 각 노드들의 연결 관계를 담은 2차원 배열 edges가 매개변수로 주어질 때, 문제에 제시된 조건에 따라 각 노드를 방문하면서 모을 수 있는 양은 최대 몇 마리인지 return 하도록 solution 함수를 완성해주세요.
  • 제한사항
    • 2 ≤ info의 길이 ≤ 17
      • info의 원소는 0 또는 1 입니다.
      • info[i]는 i번 노드에 있는 양 또는 늑대를 나타냅니다.
      • 0은 양, 1은 늑대를 의미합니다.
      • info[0]의 값은 항상 0입니다. 즉, 0번 노드(루트 노드)에는 항상 양이 있습니다.
    • edges의 세로(행) 길이 = info의 길이 - 1
      • edges의 가로(열) 길이 = 2
      • edges의 각 행은 [부모 노드 번호, 자식 노드 번호] 형태로, 서로 연결된 두 노드를 나타냅니다.
      • 동일한 간선에 대한 정보가 중복해서 주어지지 않습니다.
      • 항상 하나의 이진 트리 형태로 입력이 주어지며, 잘못된 데이터가 주어지는 경우는 없습니다.
      • 0번 노드는 항상 루트 노드입니다.

Solution

function solution(info, edges) {
    let answer = 0;
    const graph = Array.from({length: info.length}, () => []);
    
    edges.forEach(([parent, child]) => {
        graph[parent].push(child);
    });
    
    function dfs(currentNode, sheepCount, wolfCount, possible) {
        let newPossibles = [...possible];
        let currentIndex = newPossibles.indexOf(currentNode);
        
        info[currentNode]? wolfCount++ : sheepCount++;
        answer = Math.max(answer, sheepCount);
        
        if (sheepCount === wolfCount) return;
        
        newPossibles.push(...graph[currentNode]);
        newPossibles.splice(currentIndex, 1);
        
        for (const nextNode of newPossibles) {
            dfs(nextNode, sheepCount, wolfCount, newPossibles);
        }
    }
    
    dfs(0,0,0,[0]);
    
    return answer;
}
  • 풀이 방법
    1. graph 배열의 부모 노드 인덱스에 자식 노드를 넣음
    2. DFS를 사용해 모든 경로를 탐색
      • 모든 노드에 방문할 때 마다, sheepCount를 answer와 비교하여 최대값을 answer에 할당함
      • sheepCount와 wolfCount가 같은 경우, 현재 노드에서 탐색을 종료함
      • newPossibles 배열에 현재 노드를 제외하고 이동 가능한 노드를 추가함
    3. 모든 경로를 탐색 후 answer를 반환함

Problem : 보석 쇼핑

  • 어느 날 스트레스를 풀기 위해 보석 매장에 쇼핑을 하러 간 어피치는 이전처럼 진열대의 특정 범위의 보석을 모두 구매하되 특별히 아래 목적을 달성하고 싶었습니다.

    • 진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매

  • 진열대 번호 순서대로 보석들의 이름이 저장된 배열 gems가 매개변수로 주어집니다. 이때 모든 보석을 하나 이상 포함하는 가장 짧은 구간을 찾아서 return 하도록 solution 함수를 완성해주세요.

  • 가장 짧은 구간의 시작 진열대 번호와 끝 진열대 번호를 차례대로 배열에 담아서 return 하도록 하며, 만약 가장 짧은 구간이 여러 개라면 시작 진열대 번호가 가장 작은 구간을 return 합니다.

  • 제한사항

    • gems 배열의 크기는 1 이상 100,000 이하입니다.
      • gems 배열의 각 원소는 진열대에 나열된 보석을 나타냅니다.
      • gems 배열에는 1번 진열대부터 진열대 번호 순서대로 보석이름이 차례대로 저장되어 있습니다.
      • gems 배열의 각 원소는 길이가 1 이상 10 이하인 알파벳 대문자로만 구성된 문자열입니다.

Solution

function solution(gems) {
    let answer = [0, Infinity];
    const gemCount = new Set(gems).size;
    const gemMap = new Map();
    
    for (let i = 0; i < gems.length; i++) {
        gemMap.delete(gems[i]);
        gemMap.set(gems[i], i);
        
        if (gemMap.size === gemCount) {
            const startIndex = gemMap.values().next().value;
            const endIndex = i;
            
            if (endIndex - startIndex < answer[1] - answer[0]) {
                answer = [startIndex + 1, endIndex + 1];
            }
            
            gemMap.delete(gems[startIndex]);
        }
    }
    return answer;
}

Problem : 두 큐 합 같게 만들기

  • 길이가 같은 두 개의 큐가 주어집니다. 하나의 큐를 골라 원소를 추출(pop)하고, 추출된 원소를 다른 큐에 집어넣는(insert) 작업을 통해 각 큐의 원소 합이 같도록 만들려고 합니다. 이때 필요한 작업의 최소 횟수를 구하고자 합니다. 한 번의 pop과 한 번의 insert를 합쳐서 작업을 1회 수행한 것으로 간주합니다.

  • 큐는 먼저 집어넣은 원소가 먼저 나오는 구조입니다. 이 문제에서는 큐를 배열로 표현하며, 원소가 배열 앞쪽에 있을수록 먼저 집어넣은 원소임을 의미합니다. 즉, pop을 하면 배열의 첫 번째 원소가 추출되며, insert를 하면 배열의 끝에 원소가 추가됩니다. 예를 들어 큐 [1, 2, 3, 4]가 주어졌을 때, pop을 하면 맨 앞에 있는 원소 1이 추출되어 [2, 3, 4]가 되며, 이어서 5를 insert하면 [2, 3, 4, 5]가 됩니다.

  • 두 큐에 담긴 모든 원소의 합은 30입니다. 따라서, 각 큐의 합을 15로 만들어야 합니다. 예를 들어, 다음과 같이 2가지 방법이 있습니다.

    1. queue2의 4, 6, 5를 순서대로 추출하여 queue1에 추가한 뒤, queue1의 3, 2, 7, 2를 순서대로 추출하여 queue2에 추가합니다. 그 결과 queue1은 [4, 6, 5], queue2는 [1, 3, 2, 7, 2]가 되며, 각 큐의 원소 합은 15로 같습니다. 이 방법은 작업을 7번 수행합니다.
    2. queue1에서 3을 추출하여 queue2에 추가합니다. 그리고 queue2에서 4를 추출하여 queue1에 추가합니다. 그 결과 queue1은 [2, 7, 2, 4], queue2는 [6, 5, 1, 3]가 되며, 각 큐의 원소 합은 15로 같습니다. 이 방법은 작업을 2번만 수행하며, 이보다 적은 횟수로 목표를 달성할 수 없습니다.

  • 따라서 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수는 2입니다.

  • 길이가 같은 두 개의 큐를 나타내는 정수 배열 queue1, queue2가 매개변수로 주어집니다. 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수를 return 하도록 solution 함수를 완성해주세요. 단, 어떤 방법으로도 각 큐의 원소 합을 같게 만들 수 없는 경우, -1을 return 해주세요.

  • 제한사항

    • 1 ≤ queue1의 길이 = queue2의 길이 ≤ 300,000
    • 1 ≤ queue1의 원소, queue2의 원소 ≤ 10^9
    • 주의: 언어에 따라 합 계산 과정 중 산술 오버플로우 발생 가능성이 있으므로 long type 고려가 필요합니다.

Solution

function solution(queue1, queue2) {
    let answer = -1;
    let sum1 = 0;
    let sum2 = 0;
    for (let i = 0; i < queue1.length; i++) {
        sum1 += queue1[i];
        sum2 += queue2[i];
    }
    
    const target = (sum1 + sum2) / 2;
    const totalQueue = [...queue1, ...queue2];
    let pointer1 = 0;
    let pointer2 = queue1.length;
    const end = queue1.length * 3;
    
    for (let count = 0; count < end; count++) {
        if (sum1 === target) {
            return count;
        }
        
        if (sum1 > target) {
            sum1 -= totalQueue[pointer1++];
        } else {
            sum1 += totalQueue[pointer2++];
        }
    }
    
    return -1;
}

Problem : 파괴되지 않은 건물

  • N x M 크기의 행렬 모양의 게임 맵이 있습니다. 이 맵에는 내구도를 가진 건물이 각 칸마다 하나씩 있습니다. 적은 이 건물들을 공격하여 파괴하려고 합니다. 건물은 적의 공격을 받으면 내구도가 감소하고 내구도가 0이하가 되면 파괴됩니다. 반대로, 아군은 회복 스킬을 사용하여 건물들의 내구도를 높이려고 합니다.
  • 적의 공격과 아군의 회복 스킬은 항상 직사각형 모양입니다.
    예를 들어, 아래 사진은 크기가 4 x 5인 맵에 내구도가 5인 건물들이 있는 상태입니다.

  • 첫 번째로 적이 맵의 (0,0)부터 (3,4)까지 공격하여 4만큼 건물의 내구도를 낮추면 아래와 같은 상태가 됩니다.

  • 두 번째로 적이 맵의 (2,0)부터 (2,3)까지 공격하여 2만큼 건물의 내구도를 낮추면 아래와 같이 4개의 건물이 파괴되는 상태가 됩니다.

  • 세 번째로 아군이 맵의 (1,0)부터 (3,1)까지 회복하여 2만큼 건물의 내구도를 높이면 아래와 같이 2개의 건물이 파괴되었다가 복구되고 2개의 건물만 파괴되어있는 상태가 됩니다.

  • 마지막으로 적이 맵의 (0,1)부터 (3,3)까지 공격하여 1만큼 건물의 내구도를 낮추면 아래와 같이 8개의 건물이 더 파괴되어 총 10개의 건물이 파괴된 상태가 됩니다. (내구도가 0 이하가 된 이미 파괴된 건물도, 공격을 받으면 계속해서 내구도가 하락하는 것에 유의해주세요.)

  • 최종적으로 총 10개의 건물이 파괴되지 않았습니다.

  • 건물의 내구도를 나타내는 2차원 정수 배열 board와 적의 공격 혹은 아군의 회복 스킬을 나타내는 2차원 정수 배열 skill이 매개변수로 주어집니다. 적의 공격 혹은 아군의 회복 스킬이 모두 끝난 뒤 파괴되지 않은 건물의 개수를 return하는 solution함수를 완성해 주세요.

  • 제한사항

    • 1 ≤ board의 행의 길이 (= N) ≤ 1,000
    • 1 ≤ board의 열의 길이 (= M) ≤ 1,000
    • 1 ≤ board의 원소 (각 건물의 내구도) ≤ 1,000
    • 1 ≤ skill의 행의 길이 ≤ 250,000
    • skill의 열의 길이 = 6
    • skill의 각 행은 [type, r1, c1, r2, c2, degree]형태를 가지고 있습니다.
      • type은 1 혹은 2입니다.
        • type이 1일 경우는 적의 공격을 의미합니다. 건물의 내구도를 낮춥니다.
        • type이 2일 경우는 아군의 회복 스킬을 의미합니다. 건물의 내구도를 높입니다.
      • (r1, c1)부터 (r2, c2)까지 직사각형 모양의 범위 안에 있는 건물의 내구도를 degree 만큼 낮추거나 높인다는 뜻입니다.
        • 0 ≤ r1 ≤ r2 < board의 행의 길이
        • 0 ≤ c1 ≤ c2 < board의 열의 길이
        • 1 ≤ degree ≤ 500
        • type이 1이면 degree만큼 건물의 내구도를 낮춥니다.
        • type이 2이면 degree만큼 건물의 내구도를 높입니다.
    • 건물은 파괴되었다가 회복 스킬을 받아 내구도가 1이상이 되면 파괴되지 않은 상태가 됩니다. 즉, 최종적으로 건물의 내구도가 1이상이면 파괴되지 않은 건물입니다.

  • 정확성 테스트 케이스 제한 사항

    • 1 ≤ board의 행의 길이 (= N) ≤ 100
    • 1 ≤ board의 열의 길이 (= M) ≤ 100
    • 1 ≤ board의 원소 (각 건물의 내구도) ≤ 100
    • 1 ≤ skill의 행의 길이 ≤ 100
      • 1 ≤ degree ≤ 100

Solution

  • 처음 푼 풀이 (정확성 테스트 : 통과, 효율성 테스트: 시간초과)
function solution(board, skill) {
    skill.forEach(([type, r1, c1, r2, c2, degree]) => {
       for (let r = r1; r <= r2; r++) {
           for (let c = c1; c <= c2; c++) {
               if (type === 1) {
                   board[r][c] -= degree;
                   continue;
               }
               board[r][c] += degree;
           }
       }
    });
    
    answer = board.reduce((totalRuinedBuildings, rowBuildings) => {
        totalRuinedBuildings += rowBuildings.filter((durability) => durability > 0).length;
        return totalRuinedBuildings;
    }, 0);
    return answer;
}

a번째부터 b번째 구간의 합

  • sum_arr[b] = arr[0] + arr[1] + ... + arr[a-1] + arr[a] + arr[a+1] + ... + arr[b]
  • sum_arr[a-1] = arr[0] + arr[1] + ... + arr[a-1]
  • sum_arr[b] - sum_arr[a-1] = arr[a] + arr[a+1] + ... + arr[b]

  • 1차원 누적합

    • arr[i] ~ arr[j] 구간의 누적합
      • arr[i] = n
      • arr[j+1] = -n

  • 1차원 누적합 예

    • 1번째부터 4번째까지 a만큼 더하기
a-a
aaaaa-a
aaaa
  • 1차원 누적합 예 (여러 구간의 경우)
    • 1번째부터 3번째까지 a만큼 더하기
    • 2번째부터 4번째까지 b만큼 더하기
    • 3번째부터 6번째까지 c만큼 더하기
abc-a-b-c
aa+ba+b+ca+b+c-ab+c-bc-c
aa+ba+b+cb+cc
  • 2차원 누적합
    • arr[i][j] ~ arr[ii][jj] 구간의 누적합
      • arr[i][jj+1] = -n
      • arr[ii+1][j] = -n
      • arr[ii+1][jj+1] = n
    • 행방향 누적합을 계산한 후, 행 누적합에 대한 열방향 누적합 계산
function solution(board, skill) {
    let answer = 0;
    const N = board.length;
    const M = board[0].length;
    const cumSum = Array.from({length: N + 1}, () => new Array(M + 1).fill(0));
    
    skill.forEach((skillset) => {
        const minRow = skillset[1];
        const minCol = skillset[2];
        const maxRow = skillset[3] + 1;
        const maxCol = skillset[4] + 1;
        const degree = skillset[0] === 1 ? skillset[5] * -1 : skillset[5];
        const minusDegree = degree * -1;
        cumSum[minRow][minCol] += degree;
        cumSum[minRow][maxCol] += minusDegree;
        cumSum[maxRow][minCol] += minusDegree;
        cumSum[maxRow][maxCol] += degree;
    });
    
    // row cumulative sum
    for (let row = 0; row <= N; row++) {
        for (let col = 1; col <= M; col++) {
            cumSum[row][col] += cumSum[row][col - 1];
        }
    }
    
    // col cumulative sum
    for (let col = 0; col <= M; col++) {
        for (let row = 1; row <= N; row++) {
            cumSum[row][col] += cumSum[row - 1][col];
        }
    }
    
    for (let row = 0; row < N; row++) {
        for (let col = 0; col < M; col++) {
            board[row][col] += cumSum[row][col];
            if (board[row][col] > 0) {
                answer++;
            }
        }
    }
    return answer;
}

Problem : k진수에서 소수 개수 구하기

  • 양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다.

    • 0P0처럼 소수 양쪽에 0이 있는 경우
    • P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우
    • 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우
    • P처럼 소수 양쪽에 아무것도 없는 경우

  • 단, P는 각 자릿수에 0을 포함하지 않는 소수입니다.

    • 예를 들어, 101은 P가 될 수 없습니다.

  • 예를 들어, 437674을 3진수로 바꾸면 211020101011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이 있으며, 총 3개입니다. (211, 2, 11을 k진법으로 보았을 때가 아닌, 10진법으로 보았을 때 소수여야 한다는 점에 주의합니다.) 211은 P0 형태에서 찾을 수 있으며, 2는 0P0에서, 11은 0P에서 찾을 수 있습니다.

  • 정수 n과 k가 매개변수로 주어집니다. n을 k진수로 바꿨을 때, 변환된 수 안에서 찾을 수 있는 위 조건에 맞는 소수의 개수를 return 하도록 solution 함수를 완성해 주세요.

  • 제한사항

    • 1 ≤ n ≤ 1,000,000
    • 3 ≤ k ≤ 10

Solution

function solution(n, k) {
    let answer = 0;
    const kNumber = n.toString(k);
    
    const isPrime = (num) => {
        if (num < 2) {
            return false;
        }
        if (num === 2) {
            return true;
        }
        
        for (let i = 2; i <= Math.sqrt(num); i++) {
            if (num % i === 0) {
                return false;
            }
        }
        return true;
    };
    
    let candidate = '';
    
    for (let i = 0; i < kNumber.length; i++) {
        if (kNumber[i] === '0') {
            if(isPrime(Number(candidate))) {
                answer++;
            }
            candidate = '';
            continue;
        }
        candidate += kNumber[i];
    }
    if (candidate.length) {
        if(isPrime(Number(candidate))) {
                answer++;
            }
    }
    return answer;
}

profile
이소라
이전 포스트

Algorithm - Summer/Winter Coding Previous Problems

post-custom-banner

0개의 댓글