Algorithm - Programmers Problems (week 9)

Problem (lev. 1) : 달리기 경주

• 얀에서는 매년 달리기 경주가 열립니다. 해설진들은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부릅니다. 예를 들어 1등부터 3등까지 "mumu", "soe", "poe" 선수들이 순서대로 달리고 있을 때, 해설진이 "soe"선수를 불렀다면 2등인 "soe" 선수가 1등인 "mumu" 선수를 추월했다는 것입니다. 즉 "soe" 선수가 1등, "mumu" 선수가 2등으로 바뀝니다.
• 선수들의 이름이 1등부터 현재 등수 순서대로 담긴 문자열 배열 players와 해설진이 부른 이름을 담은 문자열 배열 callings가 매개변수로 주어질 때, 경주가 끝났을 때 선수들의 이름을 1등부터 등수 순서대로 배열에 담아 return 하는 solution 함수를 완성해주세요.

제한사항

• 5 ≤ players의 길이 ≤ 50,000
  • players[i]는 i번째 선수의 이름을 의미합니다.
  • players의 원소들은 알파벳 소문자로만 이루어져 있습니다.
  • players에는 중복된 값이 들어가 있지 않습니다.
  • 3 ≤ players[i]의 길이 ≤ 10
• 2 ≤ callings의 길이 ≤ 1,000,000
  • callings는 players의 원소들로만 이루어져 있습니다.
  • 경주 진행중 1등인 선수의 이름은 불리지 않습니다.

Solution

• 시간 초과한 풀이

function solution(players, callings) {
    const swapPlayer = (arr, index) => {
        const prevPlayer = arr[index - 1];
        const currPlayer = arr[index];
        arr[index - 1] = currPlayer;
        arr[index] = prevPlayer;
    }
    
    callings.forEach((calledPlayer) => {
        const calledPlayerIndex = players.indexOf(calledPlayer);
        if (calledPlayerIndex === 0) {
            return;
        }
        swapPlayer(players, calledPlayerIndex);
    });
    return players;
}

• indexOf 메서드를 사용하여 탐색하는 대신에 객체에 저장해둔 index를 접근하는 방식으로 바꾼 풀이 (참고)

function solution(players, callings) {
    const playerIndice = {};
    
    for (let index = 0; index < players.length; index++) {
        playerIndice[players[index]] = index;
    }
    
    
    callings.forEach((calledPlayer, calledPlayerIndex) => {
        const playerIndex = playerIndice[calledPlayer];
        if (playerIndex > 0) {
            const prevPlayer = players[playerIndex - 1];
            
            players[playerIndex - 1] = calledPlayer;
            players[playerIndex] = prevPlayer;
            
            playerIndice[calledPlayer] = playerIndex - 1;
            playerIndice[prevPlayer] = playerIndex;
        }
    });
    return players;
}

Problem (lev.2) : 마법의 엘리베이터

• 마법의 엘리베이터의 버튼은 특별합니다. 마법의 엘리베이터에는 -1, +1, -10, +10, -100, +100 등과 같이 절댓값이 10c (c ≥ 0 인 정수) 형태인 정수들이 적힌 버튼이 있습니다. 마법의 엘리베이터의 버튼을 누르면 현재 층 수에 버튼에 적혀 있는 값을 더한 층으로 이동하게 됩니다.
  • 단, 엘리베이터가 위치해 있는 층과 버튼의 값을 더한 결과가 0보다 작으면 엘리베이터는 움직이지 않습니다.
• 마법의 엘리베이터를 움직이기 위해서 버튼 한 번당 마법의 돌 한 개를 사용하게 됩니다.
  • 예를 들어, 16층에 있는 민수가 0층으로 가려면 -1이 적힌 버튼을 6번, -10이 적힌 버튼을 1번 눌러 마법의 돌 7개를 소모하여 0층으로 갈 수 있습니다. 하지만, +1이 적힌 버튼을 4번, -10이 적힌 버튼 2번을 누르면 마법의 돌 6개를 소모하여 0층으로 갈 수 있습니다.
• 민수와 마법의 엘리베이터가 있는 층을 나타내는 정수 storey 가 주어졌을 때, 0층으로 가기 위해 필요한 마법의 돌의 최소값을 return 하도록 solution 함수를 완성하세요.

제한사항

• 1 ≤ storey ≤ 100,000,0004

Solution

• 가장 큰 자리수에서만 한 층 더 올라가는 경우를 고려해서 문제를 풀었더니 틀렸습니다.
• 모든 자리수에서 한 층 더 올라가는 경우를 고려해야 하기 때문에 dfs를 사용해서 풀어야 합니다.

function solution(storey) {
    let answer = 100000000;
    const dfs = (number, movement) => {
        if (movement > answer) {
            return;
        }
        
        if (number === 0) {
            answer = Math.min(answer, movement);
            return;
        }
        
        const digit = number % 10;
        const quotient = Math.floor(number / 10);
        
        dfs(quotient, movement + digit);
        dfs(quotient + 1, movement + 10 - digit);
    }
    
    dfs(storey, 0);
    return answer;
}

Problem (lev. 2) : 리코쳇 로봇

• 리코쳇 로봇이라는 보드게임이 있습니다.

이 보드게임은 격자모양 게임판 위에서 말을 움직이는 게임으로, 시작 위치에서 목표 위치까지 최소 몇 번만에 도달할 수 있는지 말하는 게임입니다.

• 이 게임에서 말의 움직임은 상, 하, 좌, 우 4방향 중 하나를 선택해서 게임판 위의 장애물이나 맨 끝에 부딪힐 때까지 미끄러져 이동하는 것을 한 번의 이동으로 칩니다.
• 다음은 보드게임판을 나타낸 예시입니다.

...D..R
.D.G...
....D.D
D....D.
..D....

• 여기서 "."은 빈 공간을, "R"은 로봇의 처음 위치를, "D"는 장애물의 위치를, "G"는 목표지점을 나타냅니다.
  위 예시에서는 "R" 위치에서 아래, 왼쪽, 위, 왼쪽, 아래, 오른쪽, 위 순서로 움직이면 7번 만에 "G" 위치에 멈춰 설 수 있으며, 이것이 최소 움직임 중 하나입니다.

• 게임판의 상태를 나타내는 문자열 배열 board가 주어졌을 때, 말이 목표위치에 도달하는데 최소 몇 번 이동해야 하는지 return 하는 solution함수를 완성하세요. 만약 목표위치에 도달할 수 없다면 -1을 return 해주세요.

제한사항

• 3 ≤ board의 길이 ≤ 100
• 3 ≤ board의 원소의 길이 ≤ 100
• board의 원소의 길이는 모두 동일합니다.
• 문자열은 ".", "D", "R", "G"로만 구성되어 있으며 각각 빈 공간, 장애물, 로봇의 처음 위치, 목표 지점을 나타냅니다.
• "R"과 "G"는 한 번씩 등장합니다.

Solution

• 로봇이 갈 수 있는 위치를 고려하는 bfs 문제였습니다.
  • 로봇이 간 위치는 visited 배열에 저장하여 다시 방문하지 않도록 했습니다.
  • 게임판 위의 장애물이나 맨 끝에 부딪힐 때까지 미끄러지는 조건을 구현하는 것이 잘 생각나지 않았습니다.
  • 다른 사람 풀이를 참고하여 while 문을 사용하여 구현했습니다. (참고)

function solution(board) {
    let answer = 0;
    const queue = [];
    const n = board.length;
    const m = board[0].length;
    const dx = [-1, 1, 0, 0];
    const dy = [0, 0, -1, 1];
    const visited = Array.from({length: n}, () => new Array(m).fill(false));
    board = board.map((str) => str.split(''));
    
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (board[i][j] === 'R') {
                visited[i][j] = true;
                queue.push([i, j, 0]);
            }
        }
    }
    while (queue.length) {
        const size = queue.length;
        
        for (let i = 0; i < size; i++) {
            const [x, y, movement] = queue.shift();
            
            for (let j = 0; j < dx.length; j++) {
                let nx = x + dx[j];
                let ny = y + dy[j];
                
                while (nx >= 0 && nx < n && ny >= 0 && ny < m & board[nx][ny] !== 'D') {
                    nx += dx[j];
                    ny += dy[j];
                }
                
                nx -= dx[j];
                ny -= dy[j];
                
                if (board[nx][ny] === 'G') {
                    return movement + 1;
                }
                
                if (!visited[nx][ny]) {
                    visited[nx][ny] = true;
                    queue.push([nx, ny, movement + 1])
                }
            }
        }
    }
    
    return -1;
}

Problem (lev. 2) : 뒤에 있는 큰 수 찾기

• 정수로 이루어진 배열 numbers가 있습니다. 배열 의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 합니다.
• 정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해주세요. 단, 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다.

제한사항

• 4 ≤ numbers의 길이 ≤ 1,000,000
• 1 ≤ numbers[i] ≤ 1,000,000

Solution

• 시간 초과된 풀이

function solution(numbers) {
    const findLargeNumber = (number, index) => {
        for (let i = index + 1; i < numbers.length; i++) {
            if (numbers[i] > number) {
                return numbers[i];
            }
        }
        return -1;
    }
    
    return numbers.map((number, index) => findLargeNumber(number, index));
}

• stack을 사용하여 for 문을 하나만 사용하도록 변경합니다. (참고)

function solution(numbers) {
  const answer = new Array(numbers.length).fill(-1);
  const stack = [];
 
  for (let index = 0; index < numbers.length; index++) {
    while (stack.length && numbers[stack.at(-1)] < numbers[index]) {
      answer[stack.pop()] = numbers[index];
    }
    stack.push(index);
  }
  return answer;
}

Problem (lev. 2) : 롤케이크 자르기

• 철수는 롤케이크를 두 조각으로 잘라서 동생과 한 조각씩 나눠 먹으려고 합니다. 이 롤케이크에는 여러가지 토핑들이 일렬로 올려져 있습니다. 철수와 동생은 롤케이크를 공평하게 나눠먹으려 하는데, 그들은 롤케이크의 크기보다 롤케이크 위에 올려진 토핑들의 종류에 더 관심이 많습니다. 그래서 잘린 조각들의 크기와 올려진 토핑의 개수에 상관없이 각 조각에 동일한 가짓수의 토핑이 올라가면 공평하게 롤케이크가 나누어진 것으로 생각합니다.
• 예를 들어, 롤케이크에 4가지 종류의 토핑이 올려져 있다고 합시다.
  • 토핑들을 1, 2, 3, 4와 같이 번호로 표시했을 때, 케이크 위에 토핑들이 [1, 2, 1, 3, 1, 4, 1, 2] 순서로 올려져 있습니다.
  • 만약 세 번째 토핑(1)과 네 번째 토핑(3) 사이를 자르면 롤케이크의 토핑은 [1, 2, 1], [3, 1, 4, 1, 2]로 나뉘게 됩니다. 철수가 [1, 2, 1]이 놓인 조각을, 동생이 [3, 1, 4, 1, 2]가 놓인 조각을 먹게 되면 철수는 두 가지 토핑(1, 2)을 맛볼 수 있지만, 동생은 네 가지 토핑(1, 2, 3, 4)을 맛볼 수 있으므로, 이는 공평하게 나누어진 것이 아닙니다.
  • 만약 롤케이크의 네 번째 토핑(3)과 다섯 번째 토핑(1) 사이를 자르면 [1, 2, 1, 3], [1, 4, 1, 2]로 나뉘게 됩니다. 이 경우 철수는 세 가지 토핑(1, 2, 3)을, 동생도 세 가지 토핑(1, 2, 4)을 맛볼 수 있으므로, 이는 공평하게 나누어진 것입니다. 공평하게 롤케이크를 자르는 방법은 여러가지 일 수 있습니다.
  • 위의 롤케이크를 [1, 2, 1, 3, 1], [4, 1, 2]으로 잘라도 공평하게 나뉩니다. 어떤 경우에는 롤케이크를 공평하게 나누지 못할 수도 있습니다.
• 롤케이크에 올려진 토핑들의 번호를 저장한 정수 배열 topping이 매개변수로 주어질 때, 롤케이크를 공평하게 자르는 방법의 수를 return 하도록 solution 함수를 완성해주세요.

Solution

• 시간초과된 풀이

function solution(topping) {
    let answer = 0;
    const toppingCount = new Set(topping).size;
  
    if (toppingCount % 2 !== 0) {
        return -1;
    }
    for (let i = toppingCount / 2; i < topping.length; i++) {
        const toppingCount1 = new Set(topping.slice(0, i)).size;
        const toppingCount2 = new Set(topping.slice(i)).size;
        if (toppingCount1 === toppingCount2) {
            answer++;
        }
    }
    return answer;
}

• Map을 사용한 풀이

function solution(topping) {
    let answer = 0;
    const toppingMap = new Map();
    const broTopping = new Map();
    
    for (let curTopping of topping) {
        toppingMap.set(curTopping, (toppingMap.get(curTopping) || 0) + 1);
    }
    
    for (let curTopping of topping) {
        if (toppingMap.has(curTopping)) {
            toppingMap.set(curTopping, toppingMap.get(curTopping) - 1);
        }
        broTopping.set(curTopping, 1);
        
        if (!toppingMap.get(curTopping)) {
            toppingMap.delete(curTopping);
        }
        
        if (toppingMap.size === broTopping.size) {
            answer++;
        }
        
        if (broTopping.size > toppingMap.size) {
            break;
        }
    }
    return answer;
}

Problem (lev. 1) : 공원 산책

• 지나다니는 길을 'O', 장애물을 'X'로 나타낸 직사각형 격자 모양의 공원에서 로봇 강아지가 산책을 하려합니다. 산책은 로봇 강아지에 미리 입력된 명령에 따라 진행하며, 명령은 다음과 같은 형식으로 주어집니다.
  • ["방향 거리", "방향 거리" … ]
• 예를 들어 "E 5"는 로봇 강아지가 현재 위치에서 동쪽으로 5칸 이동했다는 의미입니다. 로봇 강아지는 명령을 수행하기 전에 다음 두 가지를 먼저 확인합니다.
  • 주어진 방향으로 이동할 때 공원을 벗어나는지 확인합니다.
  • 주어진 방향으로 이동 중 장애물을 만나는지 확인합니다.
  • 위 두 가지중 어느 하나라도 해당된다면, 로봇 강아지는 해당 명령을 무시하고 다음 명령을 수행합니다.
  • 공원의 가로 길이가 W, 세로 길이가 H라고 할 때, 공원의 좌측 상단의 좌표는 (0, 0), 우측 하단의 좌표는 (H - 1, W - 1) 입니다.

• 공원을 나타내는 문자열 배열 park, 로봇 강아지가 수행할 명령이 담긴 문자열 배열 routes가 매개변수로 주어질 때, 로봇 강아지가 모든 명령을 수행 후 놓인 위치를 [세로 방향 좌표, 가로 방향 좌표] 순으로 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

• 3 ≤ park의 길이 ≤ 50
• 3 ≤ park[i]의 길이 ≤ 50
• park[i]는 다음 문자들로 이루어져 있으며 시작지점은 하나만 주어집니다.
• S : 시작 지점
• O : 이동 가능한 통로
• X : 장애물
• park는 직사각형 모양입니다.
• 1 ≤ routes의 길이 ≤ 50
• routes의 각 원소는 로봇 강아지가 수행할 명령어를 나타냅니다.
• 로봇 강아지는 routes의 첫 번째 원소부터 순서대로 명령을 수행합니다.
• routes의 원소는 "op n"과 같은 구조로 이루어져 있으며, - op는 이동할 방향, n은 이동할 칸의 수를 의미합니다.
• op는 다음 네 가지중 하나로 이루어져 있습니다.
  • N : 북쪽으로 주어진 칸만큼 이동합니다.
  • S : 남쪽으로 주어진 칸만큼 이동합니다.
  • W : 서쪽으로 주어진 칸만큼 이동합니다.
  • E : 동쪽으로 주어진 칸만큼 이동합니다.
• 1 ≤ n ≤ 9

Solution

function solution(park, routes) {
    const directionObj = {
        'N': [-1, 0],
        'S': [1, 0], 
        'W': [0, -1], 
        'E': [0, 1]
    };
    const H = park.length;
    const W = park[0].length;
    let start;
    
    const parkMap = park.map((str, strIndex) => {
        if (!start) {
            const startIndex = str.indexOf('S');
            if (startIndex !== -1) {
                start = [strIndex, startIndex];
            }
        }
        return str.split('');
    });
    
    for (let route of routes) {
        let [name, movement] = route.split(' ');
        movement = Number(movement);
        let x = start[0];
        let y = start[1];
        let canMove = true;
        
        while (canMove && movement) {
            x += directionObj[name][0];
            y += directionObj[name][1];
            if (x < 0 || x > H -1 || y < 0 || y > W -1 || parkMap[x][y] === 'X') {
                canMove = false;
                break;
            }
            movement--;
        }
        
        if (canMove) {
            start[0] = x;
            start[1] = y;
        }
    }
    
    return start;
}