TIL - 프로그래머스 알고리즘 풀이 (1단계 : 크레인 인형뽑기 게임)

어제 2차원 배열을 탐색하는 격자판 최대합 구하기와 봉우리 문제를 풀어봤는데, 강의의 도움을 받아서 푼 문제라 새로운 2차원 배열 문제를 풀고 싶어서 찾은 크레인 인형뽑기 게임🤖

우선 문제 풀이에 직결되는 정보들은 다음과 같았다 ⬇️

👉 게임 화면은 N * N 크기의 정사각 격자이다.
👉 크레인이 멈춘 위치에서 가장 위에 있는 인형은 집어 올려져 바구니에 쌓인다.
👉 같은 모양의 인형 두개가 연속해서 쌓이게 되면 두 인형은 터트려 지면서 바구니에서 사라지게 된다.
👉 인형이 없는 곳에서 크레인을 작동시키는 경우에는 아무런 일도 일어나지 않는다.
👉 출력 값은 터트려 사라진 인형의 개수이다.

1차 풀이는 아래와 같이 배열을 돌려 newBoard에 담아서 또 bucket 에 담으려고 splice를 사용한 후 또 다시 2중 for loop을 돌리는 아주 복잡한 알고리즘이 되었다 😅 (시간 복잡도 한 2 * 2^n + n 정도..? )

function solution(board, moves) {
    var answer = 0;
    const n = board.length;
    const newBoard = [];
    const bucket = [];

    for (let i = 0; i < n; i ++) {
        const newRow = [];
        for (let j = 0; j < n; j++) {
            newRow.push(board[j][i]);
        }
        newBoard.push(newRow);
    }
    // 행으로 찾는 구조가 더 잘 그려져서 일단 배열을 90도 돌려서 newBoard에 담았다.
    
    moves.forEach(i => {
        const targetIndex = newBoard[i - 1].lastIndexOf(0) + 1;
        bucket.push(...newBoard[i - 1].splice(targetIndex, 1, 0));
    })
    // 크레인의 현 위치에서 가장 위에 있는 인형의 index를 구해 bucket에 담았다.
    
    
    const length = bucket.length;
    
    for (let i = 0; i < length - 1; i++) {
        for (let j = 0; j < bucket.length - 1; j++) {
            if (bucket[j] === bucket[j + 1]) {
                bucket.splice(j, 2);
                answer += 2;
            }
        }
    }
    // 2중 forloop으로 bucket을 순회하면서 같은 값이 있으면 출력값에 더하고 인형이 없어진 bucket을 다시 순회할 수 있도록 작성하였다. 
    
    
    return answer;
}

문제를 풀긴 풀었는데, 아래 짤이 생각나는 풀이였다ㅋㅋ

다 풀고 나서 다른 사람의 풀이를 볼 수 있었는데, for loop을 남용하지 않고 정말 깔끔하게 푼 풀이가 있어서 같이 올려보려고 한다.

function solution(board, moves) {
    let count = 0;
    let stack = [];
    // stack을 사용한 점 👍 
    
    for (let i = 0; i < moves.length; i++) {
        const now = moves[i] - 1;
        // 2차원 배열은 board[행][열]로 탐색할 수 있는데, 이렇게 now라는 변수에 고정할 열의 값을 담아주어 이해가 잘 되었다.
        
        for (let j = 0; j < board.length; j++) {
            if(board[j][now] !== 0) {
                if (stack[stack.length - 1] === board[j][now]) {
                    stack.pop();
                    count += 2;
                } else {
                    stack.push(board[j][now]);
                }
                
                board[j][now] = 0;
                break;
            }
            // 크레인이 위치해 있는 열을 위에서 아래로 탐색, 인형이 있는 경우 stack에 이미 담겨져 있는지 비교 후 같은 인형의 경우 stack에서 꺼내고 count가 2 올라간다. 다른 인형의 경우 stack에 쌓인다.
            // 크레인으로 끌어 올려진 인형의 자리는 0으로 할당한 후 break를 사용해 다음 문으로 넘긴다. break를 적절하게 사용하여 시간 복잡도도 잘 최적화 한 코드 같다. 
        }
    }
    
    return count;
}

오늘 풀이에서 배운 점 ⬇️
✏️ 2차원배열[행][열] 구조임을 다시한번 기억하고, 행을 고정해서 탐색할지, 열을 고정해서 탐색할지, 또는 둘 다 움직여햐 하는 대각선 탐색인지 생각해보고 문제를 풀기.
✏️ LIFO인 stack 또는 FIFO인 queue 등의 자료 구조를 활용하여 풀 수 있는 문제인지 생각해보기.
✏️ loop 안에서 break를 이용하여 의미 없는 탐색을 중지하고 다음 문으로 넘길 수 있는 부분은 넘겨주기.
✏️ 변수 명 직관적으로 짓기