[프로그래머스] 2019 카카오 인턴쉽 _ 크레인 인형뽑기

2021_07_18 문제 풀이

문제 URL : https://programmers.co.kr/learn/courses/30/lessons/64061

코딩테스트 연습 - 크레인 인형뽑기 게임

 

문제

 

board 판에서 moves의 원소들의 위치에 있는 제일 위에 있는 인형을 stack 형태로 담아서 저장하고, 2개 이상 중복되어 제거되는 인형들의 갯수를 리턴하는 문제였다.

 

의사코드

1. 삽질

// [[0,0,0,0,0], > board[j] === row
//  [0,0,1,0,3],
//  [0,2,5,0,1],   j가 적을 수록 높은 부분
//  [4,2,4,4,2],
//  [3,5,1,3,1]]
 
//  인형을 담을 stack 빈배열 선언 / stack
// result = 0;

//moves를 순회한다 > 
    // 변경된 배열을 저장할 빈배열 선언 temp
    // boardIndex 저장 변수 선언

    // board를 순회한다
        // board[j][moves[i - 1]]의 값이 0이 아니라면 (값이 있는 것)
          // boardIndex = j
          // board[j][moves[i - 1]] 값을 stack 에 추가해야 함
          // stack의 마지막 요소가  board[j][moves[i] - 1] 와 같다면 
            // result += 2; (이전 + 현재 값)
            // stack.pop으로 마지막 요소 제거
          // 그렇지 않다면
            // stack에 board[j][moves[i] - 1] 를 추가한다

          // 나머지 인덱스들을 이어 붙여야 함 /
            // temp = board[j].slice(0, moves[i] - 1).concat([0, ...board[j].slice(moves[i] - 1) / 깊은복사 가공
            // 반복문 종료 break

    // board = board.slice(0, j).concat([...temp, board.slice(j)])  / 다시 재가공해서 할당한다
// result를 리턴한다

처음에 작성했던 의사 코드였다. 이중 배열을 가지고 있기때문에 얕은복사를 방지하기 위해 array 프로토타입 메소드 slice, concat으로 핸들링을 해야 한다고 생각했다. 

temp 변수에 뺀 인형의 위치에 0을 넣고 이어 붙이고.. 저장해놓은 다음 board 매개변수에 또 이어붙여서 재할당하는 방식이었는데 말도안되는 코드였다.

디버깅 도중 자바스크립트의 깊은 복사, 얕은 복사에 대해 알고있던 개념에 오류가 있다는 것을 발견했고, 

https://www.digitalocean.com/community/tutorials/copying-objects-in-javascript 

Copying Objects in JavaScript | DigitalOcean

개념을 다시 한 번 확인하는 시간을 가졌다.

2. 최종 

// [[0,0,0,0,0], > board[j] === row
//  [0,0,1,0,3],
//  [0,2,5,0,1],   j가 작을 수록 높은 부분
//  [4,2,4,4,2],
//  [3,5,1,3,1]]
 
//  인형을 담을 stack 빈배열 선언 / stack
// result = 0;

//moves를 순회한다 > let i 
    // board를 순회한다 let j
       // board[j][moves[i] - 1] 값은 빼내야 하는 보드판 열
       // 해당 열의 값이 0이 아니라면, 가장 높은 곳에 위치한 인형으로 작업 수행
         // 스택에 마지막으로 담겨져 있는 값과 열의 값이 일치하는 지 확인
            // 일치한다면, 가장 마지막에 담은 인형과 현재 인형이 2개로 중복되는 것
                // 고로 stack의 마지막 요소를 (이전에 담은 인형) 제거
                // result에 2를 더한다 (이전 인형 + 현재 인형의 갯수가 2)
            // 그게 아니라면 stack에 현재 인형의 값을 추가한다
         // board[j][moves[i] - 1] = 0; > 인형을 제거한 위치에 0을 할당
         // 반복문을 빠져 나온다
    
// result를 리턴한다

board 매개변수에 0을 할당하여 메모리에 저장되어있는 값을 변경, board의 원문 배열의 값이 변화할 수 있도록 진행했고, 뽑은 인형들을 저장하는 로직은 1차와 동일하게 stack 자료구조를 사용, 중복되는 인형이라면 array.pop()메소드로 값을 제거하고, 중복되지 않은 인형이라면 push 메소드로 인형을 넣어줄 수 있도록 구현했다.

 

풀이

function solution(board, moves) {
    let stack = [];
    let result = 0;
    
    for (let i = 0; i < moves.length; i++) {
        for (let j = 0; j < board.length; j++) {
            let target = board[j][moves[i] - 1];
            
            if (target !== 0) {
                if (stack[stack.length - 1] === target) {
                    stack.pop();
                    result += 2;
                } else {
                    stack.push(target);
                }
                board[j][moves[i] - 1] = 0;
                break;
            }
            
        }
    }
    return result;
}

시간복잡도 O(n^2) 의 코드를 구현했다.

이차원 배열을 1차원 배열로 수정하고 O(n)의 코드로 만들 수 있지 않나라는 생각을 했다가 row, col 형태의 보드판이기때문에 다른 아이디어가 떠오르지 않아 이중 반복문을 사용했다.

부족했던 깊은 복사 / 얕은 복사에 대해 다시금 정리할 수 있는 시간을 가질 수 있어 참 다행이었다.