카카오크레인 문제(stack개념)
in Algorithm
게임 화면의 격자의 상태가 담긴 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));
끝이 막힌 구덩이라고 생각하고 풀면되는 스택문제.
영상이 아니면 진짜 너무 헷갈리네…
출처 : 자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)를 보고 작성!