크레인 인형뽑기 게임 - 2019 카카오 겨울 인턴쉽

 

문제 읽으며 생각한 풀이 방향성!!!!

 

1. 전달받는 board의 배열이 moves 값으로 인덱싱하기에 용이하지 못하다고 판단!

board[row][col]에서 board[col][row]로 조회할 수 있도록 변경!!

 

2. 100 * 100 까지 가능하므로 Array 인덱싱보단 Map으로 column 조회가 좋지 않을까? 라고 생각!

아래 코드와 같이 boardMap을 구현함!

let boardMap = {};
board.forEach((row,i)=>{
    row.forEach((val,j)=>{
        if(val !== 0){
            boardMap[j+1] ?
                boardMap[j+1].push(val) :
                boardMap[j+1] = [val];
        }
    })
})

 

0 인 경우엔 넣지 않고, row를 0번부터 인덱싱 하기 위해 push를 사용해 뒤에 인형을 추가!

그러면 다음과 같이 map[col]으로 조회하면 된다.

 

 

3. 마지막으로 moves를 반복문으로 돌려 같은 인형이 나오면 제거해주는 방법을 이용하면 된다!

let dolls = [];
const answer = moves.reduce((acc, move, idx)=>{
    const shift = boardMap[move].shift();
    if(shift){
        if(dolls[0] === shift){
           dolls.shift();
           acc += 2;
        }else {
            dolls.unshift(shift);
        }   
    }
    return acc
}, 0)

 

 

shift를 이용해 배열의 맨 앞의 요소를 빼낸 후에, dolls에 맨 앞에 있는 인형과 같은지 체크하여

같으면 터뜨린 후 카운트하고, 다르면 unshift를 이용하여 앞에서 넣는 과정을 반복한다!

 

 

20분정도 소요하여 풀이 완료했다! (한 방에 성공!)

 

다른 사람의 풀이를 가져오니 아래와 같은 결과가 나왔는데 조금 더 빠른 속도를 얻음을 확인했는데 아마도 Map을 이용한 조회를 사용해서 그러지 않을까 라고 생각이 든다

 

 

전체 풀이

function solution(board, moves) {
    let boardMap = {};
    let dolls = [];
    board.forEach((row,i)=>{
        row.forEach((val,j)=>{
            if(val !== 0){
                boardMap[j+1] ?
                    boardMap[j+1].push(val) :
                    boardMap[j+1] = [val];
            }
        })
    })
    
    const answer = moves.reduce((acc, move, idx)=>{
        const shift = boardMap[move].shift();
        if(shift){
            if(dolls[0] === shift){
                dolls.shift();
                acc += 2;
            }else {
                dolls.unshift(shift);
            }   
        }
        return acc
    }, 0)
    
    return answer;
}