값들이 쌓이는 부분(바구니)을 맨 처음 배열로 구현하고, 모든 값들이 쌓이고나서 같은 값들이 인접할 경우 제거 되는 logic을 구현했는데 잘 풀리지 않았다. 고민해보니 바구니에서 궁금한 값은 가장 최근에 들어간 마지막 값이고 이 값을 효과적으로 다루는 stack을 통해서 구현해보자는 생각이 들었다.
Stack<Integer>res = new Stack();
또한 각 line에서 제일 높은 부분을 height 배열을 만들어서
가장 먼저 값이 나오는 지점을 높이로 설정했다.
ex) 5x5크기에서 index가 1에서 최초로 값이 등장했다면.
높이 = 5 - 1 =4 가 된다.
int [] height = new int[board.length];
Arrays.fill(height,0);
for(int i=0; i<board.length;i++){
for(int j=0; j<board[i].length; j++){
if(board[i][j]!=0 && height[j]==0){
height[j]=board.length-i;
}
}
}
해당 line의 높이가 0인경우에는 그 line에는 더이상 인형이 없으므로 continue
바구니에 값이 없는 경우(res.size()==0) 에는 무조건 stack에 값을 추가
아닌 경우에는 가장 위에값과, 지금 추가하려는 값이 같은경우에는 가장 위에있는 값을 pop시키고 아닌경우에는 push한다.
for(int i=0; i<moves.length; i++){
if(height[moves[i]-1]==0){
continue;
}
if(board[board.length-height[moves[i]-1]][moves[i]-1]!=0){
if(res.size()==0){
res.push(board[board.length-height[moves[i]-1]][moves[i]-1]);
}else{
if(res.peek()==board[board.length-height[moves[i]-1]][moves[i]-1]){
res.pop();
answer+=2;
}else{
res.push(board[board.length-height[moves[i]-1]][moves[i]-1]);
}
}
height[moves[i]-1]--;
}
}
import java.util.*;
class Solution {
public int solution(int[][] board, int[] moves) {
int answer = 0;
Stack<Integer>res = new Stack();
int [] height = new int[board.length];
Arrays.fill(height,0);
for(int i=0; i<board.length;i++){
for(int j=0; j<board[i].length; j++){
if(board[i][j]!=0 && height[j]==0){
height[j]=board.length-i;
}
}
}
//System.out.println(Arrays.toString(height));
for(int i=0; i<moves.length; i++){
if(height[moves[i]-1]==0){
continue;
}
if(board[board.length-height[moves[i]-1]][moves[i]-1]!=0){
if(res.size()==0){
res.push(board[board.length-height[moves[i]-1]][moves[i]-1]);
}else{
if(res.peek()==board[board.length-height[moves[i]-1]][moves[i]-1]){
res.pop();
answer+=2;
}else{
res.push(board[board.length-height[moves[i]-1]][moves[i]-1]);
}
}
height[moves[i]-1]--;
}
}
//System.out.println(res.toString());
return answer;
}
}