카카오크레인 문제(stack개념)




카카오크레인문제

게임 화면의 격자의 상태가 담긴 2차원 배열 board와 인형을 집기 위해 크레인을 작동시킨 위 치가 담긴 배열 moves가 매개변수로 주어질 때, 크레인을 모두 작동시킨 후 터트려져 사라진 인형의 개수를 return 하도록 solution 함수를 완성해주세요.



Solution

function solution(board, moves){
    let answer=0;
    let stack=[];
  //맨날 헷갈린다.. 행이 가로 열이 세로
  //moves는 몇번째 열을 선택할건지에 대한 배열.
  //board는 몇번째 행과 열에 대한 값이 들어있는 배열
    moves.forEach(pos => {	//moves배열을 forEach로 돌리고, 엘리먼트들은 pos로 받기
        for(let i=0; i<board.length; i++){	//열은 정해져 있으니 행을 돌려주자
            if(board[i][pos-1]!==0){	//board배열의 행은 i번쨰, 열은 pos-1번째 좌표가 0이 아니라면
                let tmp=board[i][pos-1];	//임시로 잠깐 숫자 넣어서 인형을 옮겨담은 통(=stack)이랑 비교해야함
                board[i][pos-1]=0;	//인형을 뽑게 되면 그 좌표는 0이 되어야 한다
                if(tmp===stack[stack.length-1]){	//인형을 옮겨담은 통에 들어있는 넘버가 새로들어온 인형의 넘버와 같다면
                    stack.pop(); //기존에 들어있는 인형은 사라져야한다.
                    answer+=2;	//기존의 인형(=stack)과 새로들어온 인형(temp)의 갯수를 더해줘야하므로 +2
                }else{
                  stack.push(tmp);
                } 
                break;	//안걸어주면 하나 뽑고 멈추는게 아니라 for문에 의해 계속해서 뽑게된다. (예를들어 1열에서 4를 뽑으면 거기서 끝나야하는데 3도 뽑으러감)
            }
        }
    });
                    
    return answer;
}

let a=[[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]];

let b=[1, 5, 3, 5, 1, 2, 1, 4];
console.log(solution(a, b));




끝이 막힌 구덩이라고 생각하고 풀면되는 스택문제.

영상이 아니면 진짜 너무 헷갈리네…






출처 : 자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)를 보고 작성!




© 2018. by sora

Powered by sora