프로그래머스: 크레인 인형뽑기 게임 - javascript (구현)

문제 출처 

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

프로그래머스

문제 풀이 힌트 

- 단순 구현 문제다. 

- 재빨리 예시를 보며 문제를 간단하게 이해하고 구현할 필요가 있다.  (자세히 보면서 길게 끌지 말자) 

 

- moves를 반복문으로 돌고, 그 안에서 board로 인형이 있는지 반복문이 돈다 

=> 시간복잡도는 O(N * M)이다. 

  - N은 moves의 최대 1000 값을 넣어보자. 

  - M은 board의 열의 길이 최대 30 값을 넣어보자. 

=> 코드의 연산 횟수는 30000번이다. 

=> js에서 초당 수행할 수 있는 연산의 수는 대략 1억(100,000,000)번 10^8번으로 가정하니, 1억 번에 비해 매우 작다.  충분히 실행 가능 !!!!! 

 

문제 풀이 코드 

function solution(board, moves) {
    const stack = []; //뽑은 인형 쌓아두기 
    let answer = 0; //터트려서 사라진 인형 개수 
    for(let move of moves){
        let j = move-1; //board 좌표에 맞게 -1 
        let result = deleteDoll(j); //j열을 인형을 없앤다. 결과 값: j열에 인형이 있다면 뽑아야 하는 인형 좌표가 나온다. 
        let x,y //뽑아야 하는 인형 봐표 값을 넣어줄 것임. 
        if(result !== false){//뽑아야 하는 인형이 있다면
            [x,y] = result; //해당 좌표 x,y에 할당. 
            let doll = board[x][y]; //해당 인형 숫자를 doll에 할당 
             board[x][y] = 0; //board에서 인형 빼기 
        if(stack[stack.length-1] === doll){//만약 stack에 있는 마지막 인형과 지금 뽑은 인형이 같다면
            stack.pop(); //stack에 있는 인형을 빼고 
            answer+=2; //터트려서 사라진 인형 개수 +2 를 해준다. 
        }else{//인형이 같지 않다면
            stack.push(doll);   //뽑은 인형을 넣는다. 
        }
      } 
    }
    return answer; 
    
    function deleteDoll(j){//주어진 열에 인형이 있다면 빼야 하는 인형 좌표값 return 
        for(let i=0; i<board.length; i++){
            if(board[i][j] !== 0) return [i,j]
        }
        return false; 
    }
}

Only 풀이 코드 

function solution(board, moves) {
    const stack = []; 
    let answer = 0; 
    for(let move of moves){
        let j = move-1; 
        let result = deleteDoll(j); 
        let x,y
        if(result !== false){
            [x,y] = result; 
            let doll = board[x][y]; 
             board[x][y] = 0; 
        if(stack[stack.length-1] === doll){
            stack.pop(); 
            answer+=2; 
        }else{
            stack.push(doll);     
        }
      } 
    }
    return answer; 
    
    function deleteDoll(j){
        for(let i=0; i<board.length; i++){
            if(board[i][j] !== 0) return [i,j]
        }
        return false; 
    }
}