일일코테 Day2, 크레인 인형뽑기 게임 - 프로그래머스(레벨1)

이틀 연속으로 일일 코드 테스트를 풀었다! 야호!! (하루만 더 하면 작심 삼일은 달성)

 

programmers.co.kr/learn/courses/30/lessons/64061

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

문제

아래와 같이 board에는 2차원 배열로 인형의 모양이 들어있고, moves 에는 각각 인형을 뽑을 위치가 들어 있다. 

// board
[[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]]

// Moves
[1,5,3,5,1,2,1,4]

// result
4

가장 오른쪽에는 인형을 순서대로 담으면 된다.

우선 해결해야할 문제들을 정리해 봤다.

- 크래인의 위치로 부터 인형을 위치에 접근하기

- 뽑은 인형들을 유지하기

크래인의 위치로 인형의 인형의 모양 얻기

우선 두가지 방법이 떠올랐다.

- 가장 위에서 부터 아래로 하나씩 인형이 있는지 확인 하는 방법

- 미리 각 위치의 인형들을 스택에 넣어뒀다가 위에서 부터 하나씩 뺴는 방법.

 

첫 번째 방법은 매번 맨 위에서부터 아래로 인형을 찾을 때까지 비교를 해야 하므로 최대 moves의 개수 x 최대 깊이 만큼의 시간이 걸린다. 

즉 인형에 접근 하는 시간은 O(H) 만큼의 복잡도를 가지고 이를 N번 해야 하므로 O(H) x O(N) 만큼의 복잡도가 소요될것 같았다.

 

두 번째 방법은 접근 하는 시간을 줄이기 위해서 미리 스택에 넣고 실제 접근할 떄는 하나씩 pop() 연산으로 꺼내는 것이다. 이 방법은 O(1)의 시간 복잡도를 가지지만 모든곳의 스택을 구성하는데 O(HxW)만큼의 시간이 걸린다. 

 

결국 이 둘의 차이는 W와 N중에 작은것을 선택하는게 유리하다는 생각이 들었다.

 

문제에서 N은 1000이하 넒이 W는 30개 이하 이므로 N이 W보다 훨씬 크다. 그래서 두번째 접근 방법을 선택하기로 결정.

뽑은 인형들을 보관

인형은 단순히 하나씩 쌓아 뒀다가 가장 최근에 넣은 인형과 현재 잡은 인형을 비교하여 같으면 인형 두개를 다시 없애면 되므로 스택자료구조를 사용하면 간단하게 해결 할 수 있다.

메모리 사용

각각 사용하는 메모리가 얼마나 될 지 고민해 봤다. 첫 번째 방법은 그냥 입력으로 들어온 배열을 사용하면 되므로 추가적인 메모리는 뽑은 인형을 유지하는데에만 하면 된다.

 

인형들을 스택에 넣는 방법은 HxW 만큼의 공간을 차지한다. 즉 최대 1Byte x 30 x 30 = 900 Byte 만큼의 추가 공간을 더 사용한다.구현 

 

구현하기

스택으로 무엇을 사용할까? 사실 JS로 문제를 풀때 바로 스택으로 무엇을 사용해야할지 떠오르지 않았다. 그래서 우선 Javascript Array에 pop() 이라는 메소드가 있는지 간단히 검색을 해봤다. 결론은 자바스크립트의 배열을 스택으로 사용할 수 있었다.

 

다음은 실제 구현

function solution(board, moves) {
    var stacksForX = [];
    const height = board.length;
    const width = board[0].length;
    const EMPTY_CELL = 0;
    
    // init board using stacks
    for (let x = 0; x < width; ++x) {
        stacksForX[x] = [];
    }
    
    // fill the new stack board
    // highest row number is bottom 
    for (let x = 0; x < width; ++x) {
        // from bottom (height -1) to top (0)
        for ( let y = height - 1; y >= 0; --y) {
            const doll = board[y][x];
            if (doll === EMPTY_CELL) {
                break;
            }
            stacksForX[x].push(doll);
        }
    }
    
    // move dolls
    const basket = [];
    var answer = 0;
    for (let x of moves) {
        const stack = stacksForX[x-1];
        const doll = stack.pop();
        if (!doll) {
            continue;
        }
        // console.log(`${doll} at ${x-1}`);
        if (basket.length === 0) {
            basket.push(doll);
        } else {
            if (basket[basket.length-1] === doll) {
                basket.pop();
                answer += 2;
            } else {
                basket.push(doll);
            }
        }
    }
    
    return answer;
}

실제 구현은 틀별 할게 없다. 

- 보드를 스택을 사용하여 재구성 한다.

- moves에 들어온 위치에 따라 인형을 하나씩 꺼낸다.

- 꺼낸 인형들을 바구니 스택에 추가한다.

- 바구니 스택에 넣을때 가장 최근의 인형모양과 현재 꺼낸 인형 모앙이 동일 하다면 바구니에서 인형을 도로 꺼내고 없어진 인형을 카운트 한다.

 

테스트를 모두 통과 하였다.

실수

사실 문제를 풀면서 한번에 테스트를 모두 통과하지 못했다. 몇 가지 실수를 하게 되었는데 다음과 같다.

- 인형이 없는 경우의 처리를 하지 않아 바구니에 undefine가 쌓이는 문제

- 터진 인형의 개수를 리턴해야 하는데 터진 횟수를 리턴하였다.

- 크래인의 위치를 0부터 센다고 가정하고 코드를 작성하니 outofindex 예외가 발생 하였다.

 

개선점

위의 실수들을 개선하려면 어떻게 해야하는지 생각을 해보았다.

- 문제에서 언급된 예외 상황을 구현 Todo로 작성을 하고 구현할때 하나씩 지워나간다.

- 결과값의 조건을 자세히 읽어보고 이 역시 Todo로 적어놓고 최종 구현했을대 확인을 하고 구현이 완료되면 Todo 리스트에서 지운다.

- 예외 상황을 쉽고 빠르게 테스트 할 수 있는 테스트케이스를 어떻게 만들어 보자.

- 배열의 인덱스가 어디서 부터 시작하는지 적어두자.

 

테스트 케이스

인형이 없는경우의 처리는 board: [[0, 0, 0], [0, 0, 0], [1, 1, 0]], moves: [1, 1 ,2] 와 같이 가장 단순한 경우 예외 테스트를 만들 수 있다.

 

개선할 점

테스트를 마치고 더 개선할 점이 없는지 생각해 보았다.

 

첫 째로 인형을 접근할때 스택에 인형을 미리 넣어 두지 않아도 최초 한번만 위에서 부터 검사를 하고 나중에는 최종 인덱스를 기억하여 스택처럼 구현할 수도 있었다. 그렇다면 거의 1k의 메모리를 절약 할 수 있다.

 

두 번째로는 배열에서 인형이 있는 지점을 찾는 방식으로 바이너리 서치를 사용하면 보드를 초기화 하는 시간을 O(logN)까지 단축할 수도 있겠다라는 생각이 들었다.

 

끝으로 번째는 코드를 좀 더 정리를 해보았다.

const EMPTY_CELL = 0;

function solution(board, moves) {
  const stackBoard = StackBoard(board);
    
  const basket = new Basket();
  var answer = 0;
  for (let x of moves) {
    const doll = stackBoard.getDoll(x);
    if (!doll) {
      continue;
    }
        
    if (basket.top() === doll) {
      basket.pop();
      answer += 2;
    } else {
      basket.push(doll);
    }
  }    
  return answer;
}

class StackBoard {
  constructor(board) {
    this.stackForX = [];
    this.height = board.length;
    this.width = board[0].length;

    // create stacks
    for (let x = 0; x < width; ++x) {
      this.stacksForX[x] = [];
    }
    
    this.fillStacks(board);
  }
  
  fillStacks(board) {
    for (let x = 0; x < width; ++x) {
      // from bottom (height -1) to top (0)
      for ( let y = height - 1; y >= 0; --y) {
        const doll = board[y][x];
        if (doll === EMPTY_CELL) {
          break;
        }
      
        this.stacksForX[x].push(doll);
      }
    }
  }
  
  getDollAt(x) {
    return stackBoard.getDoll(x-1);
  }
}

class Basket {
  constructor() {
     this.basket = [];
  }
  
  push(doll) {
    this.basket.push(doll);
  }
  
  top() {
    return this.basket.length ? this.basket[basket.length - 1] : EMPTY_CELL;
  }
  
  pop() {
    return this.basket.pop();
  }
}

사실 전체적인 코드는 개선 후가 더 복잡하다. 하지만 solution() 함수 코드를 보면 전체적인 알고리즘 흐름을 볼 수 있다.

- 보드를 초기화 한다.

- 주어진 위치의 인형을 꺼낸다.

- 바구니에서 꺼내 비교하고 동일한 경우면 사라지고 그렇지 않으면 인형을 바구니에 담는다.

라는 과정들이 코드를 보고 이해할 수 있는것 같았다.

 

실제로 종이에 적어가면서 하나하나 해겨해 보았다.

막상 블로그 글로 적으려니까 쉽지 않네.. 적지 말까..?