알고리즘

[프로그래머스] 지게차와 크레인 - JavaScript

BGK97 2025. 2. 24. 13:33

문제 출처

https://school.programmers.co.kr/learn/courses/30/lessons/388353

 

프로그래머스

SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프

programmers.co.kr

문제 설명

A 회사의 물류창고에는 알파벳 대문자로 종류를 구분하는 컨테이너가 세로로 n 줄, 가로로 m줄 총 n x m개 놓여 있습니다. 특정 종류 컨테이너의 출고 요청이 들어올 때마다 지게차로 창고에서 접근이 가능한 해당 종류의 컨테이너를 모두 꺼냅니다. 접근이 가능한 컨테이너란 4면 중 적어도 1면이 창고 외부와 연결된 컨테이너를 말합니다.

최근 이 물류 창고에서 창고 외부와 연결되지 않은 컨테이너도 꺼낼 수 있도록 크레인을 도입했습니다. 크레인을 사용하면 요청된 종류의 모든 컨테이너를 꺼냅니다.

위 그림처럼 세로로 4줄, 가로로 5줄이 놓인 창고를 예로 들어보겠습니다. 이때 "A", "BB", "A" 순서대로 해당 종류의 컨테이너 출고 요청이 들어왔다고 가정하겠습니다. “A”처럼 알파벳 하나로만 출고 요청이 들어올 경우 지게차를 사용해 출고 요청이 들어온 순간 접근 가능한 컨테이너를 꺼냅니다. "BB"처럼 같은 알파벳이 두 번 반복된 경우는 크레인을 사용해 요청된 종류의 모든 컨테이너를 꺼냅니다.

위 그림처럼 컨테이너가 꺼내져 3번의 출고 요청 이후 남은 컨테이너는 11개입니다. 두 번째 요청은 크레인을 활용해 모든 B 컨테이너를 꺼냈음을 유의해 주세요. 세 번째 요청이 들어왔을 때 2행 2열의 A 컨테이너만 접근이 가능하고 2행 3열의 A 컨테이너는 접근이 불가능했음을 유의해 주세요.

처음 물류창고에 놓인 컨테이너의 정보를 담은 1차원 문자열 배열 storage와 출고할 컨테이너의 종류와 출고방법을 요청 순서대로 담은 1차원 문자열 배열 requests가 매개변수로 주어집니다. 이때 모든 요청을 순서대로 완료한 후 남은 컨테이너의 수를 return 하도록 solution 함수를 완성해 주세요.

제한사항

  • 2 ≤ storage의 길이 = n ≤ 50
    • 2 ≤ storage[i]의 길이 = m ≤ 50
      • storage[i][j]는 위에서 부터 i + 1번째 행 j + 1번째 열에 놓인 컨테이너의 종류를 의미합니다.
      • storage[i][j]는 알파벳 대문자입니다.
  • 1 ≤ requests의 길이 ≤ 100
    • 1 ≤ requests[i]의 길이 ≤ 2
    • requests[i]는 한 종류의 알파벳 대문자로 구성된 문자열입니다.
    • requests[i]의 길이가 1이면 지게차를 이용한 출고 요청을, 2이면 크레인을 이용한 출고 요청을 의미합니다.

테스트 케이스 구성 안내

아래는 테스트 케이스 구성을 나타냅니다. 각 그룹 내의 테스트 케이스를 모두 통과하면 해당 그룹에 할당된 점수를 획득할 수 있습니다.

입출력 예 설명

입출력 예 #1

문제 설명의 예시와 같습니다.

입출력 예 #2

창고의 초기 상태와 모든 요청을 수행한 뒤의 상태입니다. 남은 컨테이너의 수인 4를 return 해야 합니다.

문제 풀이

  • 크레인이야 배열을 완탐하여 있는 값만 삭제하면 되니까 쉬웠지만, 지게차방식에서 dfs를 사용했다가 시간초과가 나서 bfs로 변경하여 문제를 풀이하였다.
  • 크레인을 사용할 때는 set을 이용해서, 해당 명령이 set안에 요소로 있을 때만 순환하도록 하여 가지치기를 수행하였다.

DFS를 활용한 풀이(배열 크면 시간 초과)

const dr = [-1 ,1, 0, 0];
const dc = [0, 0, -1, 1];
let answer = 0;
let deleteArray = new Array();
function solution(storage, requests) {
    let r = storage.length;
    let c = storage[0].length;
    let arr = Array.from(Array(r), () => Array(c).fill(null));
    let visited = Array.from(Array(r), () => Array(c).fill(false));
    const alpha = new Set();
    
    for(let i = 0; i < r; i++){
        for(let j = 0; j < c; j++){
            arr[i][j] = storage[i].charAt(j);          
            //셋에 추가해서 알파벳 저장(중복X)
            if(!alpha.has(arr[i][j])){
                alpha.add(arr[i][j]);
            }
        }
    }
    
    requests.forEach((request) => {
        deleteArray = [];
        //크레인
        if(request.length === 2){
            let com = request.charAt(0);
            useCrain(com, alpha, arr, r, c);
        }
        //지게차
        else {
            for(let i = 0; i < r; i++){
                for(let j = 0; j < c; j++){
                    //지게차 수행
                    if(request === arr[i][j]){
                        let check = useForkLift(arr, visited, i, j, r, c);
                        if(check){
                            deleteArray.push([i, j]);
                        }
                    }       
                }
            }
            //삭제배열을 한꺼번에 처리한다.
            deleteArray.forEach((element) => {
                arr[element[0]][element[1]] = "0";
                answer++;
            });
        }
    })
    
    return (r * c) - answer;
}

//크레인 사용(모든 요소 다꺼내기)
function useCrain(command, alphaSet, arr, r, c){
    //해당 요소가 set에 아직 있는 경우에만 수행
    if(alphaSet.has(command)){
        for(let i = 0; i < r; i++){
            for(let j = 0; j < c; j++){
                if(command === arr[i][j]){
                    arr[i][j] = "0";
                    answer++;
                }
            }
        }
        alphaSet.delete(command);
    }
}

//지게차 사용(외부와 맞닿은 부분만 꺼내기 가능)
function useForkLift(arr, visited, i, j, r, c){
    
    for(let d = 0; d < 4; d++){
        let nr = i + dr[d];
        let nc = j + dc[d];

        //경계를 벗어날 수 있다면 바로 return(꺼낼 수 있음)
        if(nr < 0 || nr >= r || nc < 0 || nc >= c){
            return true;
        }
        //경계를 벗어나지 않고 "0"이라면 한번 더 수행한다.
        if(nr >= 0 && nr < r && nc >= 0 && nc < c && arr[nr][nc] === "0" && !visited[nr][nc]){
            visited[nr][nc] = true;
            if(useForkLift(arr, visited, nr, nc, r, c)){
                return true;
            }
            visited[nr][nc] = false;           
        }   
    }
    return false;
}

dfs

BFS를 활용한 풀이

const dr = [-1 ,1, 0, 0];
const dc = [0, 0, -1, 1];
let answer = 0;
let deleteArray = new Array();
function solution(storage, requests) {
    let r = storage.length;
    let c = storage[0].length;
    let arr = Array.from(Array(r), () => Array(c).fill(null));
    const alpha = new Set();
    
    for(let i = 0; i < r; i++){
        for(let j = 0; j < c; j++){
            arr[i][j] = storage[i].charAt(j);          
            //셋에 추가해서 알파벳 저장(중복X)
            if(!alpha.has(arr[i][j])){
                alpha.add(arr[i][j]);
            }
        }
    }
    
    requests.forEach((request) => {
        deleteArray = [];
        //크레인
        if(request.length === 2){
            let com = request.charAt(0);
            useCrain(com, alpha, arr, r, c);
        }
        //지게차
        else {
            for(let i = 0; i < r; i++){
                for(let j = 0; j < c; j++){
                    //지게차 수행
                    if(request === arr[i][j]){
                        let check = useForkLift(arr, i, j, r, c);
                        if(check){
                            deleteArray.push([i, j]);
                        }
                    }       
                }
            }
            //삭제배열을 한꺼번에 처리한다.
            deleteArray.forEach((element) => {
                arr[element[0]][element[1]] = "0";
                answer++;
            });
        }
    })
    
    return (r * c) - answer;
}

//크레인 사용(모든 요소 다꺼내기)
function useCrain(command, alphaSet, arr, r, c){
    //해당 요소가 set에 아직 있는 경우에만 수행
    if(alphaSet.has(command)){
        for(let i = 0; i < r; i++){
            for(let j = 0; j < c; j++){
                if(command === arr[i][j]){
                    arr[i][j] = "0";
                    answer++;
                }
            }
        }
        alphaSet.delete(command);
    }
}

//지게차 사용(외부와 맞닿은 부분만 꺼내기 가능) bfs로 탐색
function useForkLift(arr, i, j, r, c){
    let visited = Array.from(Array(r), () => Array(c).fill(false));
    const queue = [[i, j]];
    visited[i][j] = true;
    
    while(queue.length > 0){
        const [curR, curC] = queue.shift();
        
        //순환
        for(let d = 0; d < 4; d++){
            let nr = curR + dr[d];
            let nc = curC + dc[d];
            
            //경계를 벗어날 수 있다면 바로 return(꺼낼 수 있음)
            if(nr < 0 || nr >= r || nc < 0 || nc >= c){
                return true;
            }
            
            //경계를 벗어나지 않고 "0"이라면 한번 더 수행한다.
            if(nr >= 0 && nr < r && nc >= 0 && nc < c && arr[nr][nc] === "0" && !visited[nr][nc]){
                visited[nr][nc] = true;
                queue.push([nr, nc]);
            }   
        }
    }
    
    return false;
}

결과

회고

  • Js로는 dfs든 bfs든 아직 어렵다!
저작자표시 비영리 동일조건 (새창열림)