[코딩연습_JAVA] 크레인 인형뽑기

*김태원님의 '자바 알고리즘 문제풀이 입문'으로 공부중이다.

[간단 문제 설명]
n*n 크기의 2차원 배열에 다양한 종류의 인형이 들어있다. 크레인으로 인형을 집어 1차원 배열에 넣는다.
이때 만약 같은 종류의 인형이 직접 맞닿으면 그 두 인형은 사라진다.
크레인이 모두 작동한 후 사라진 인형의 개수를 구하라.

 

 

 

내 솔루션 코드:

   public int solution(int n, int[][] board, int[] moves){
       Stack<Integer> stack= new Stack<>();
       int answer=0;

       int y=0; //2차원 배열의 행을 나타냄
       for(int x: moves){
           while(y<n && board[y][x-1]==0){
               y++;
               if(y==n) break;
           }
           if(y==n) {
               y=0; //크레인 초기화
               continue;
           }
           stack.push(board[y][x-1]);
           board[y][x-1]=0; //인형이 뽑힌 자리는 0으로 초기화
           y=0; //크레인 초기화

           if(stack.size()>1 && stack.get(stack.size()-2)==stack.peek()){
               stack.pop();
               stack.pop();
               answer+=2;
           }
       }
       
       return answer;
   }

[아이디어 설명]
1) 크레인으로 인형을 잡아서 Stack에 넣는다.
   (이후 크레인 위치는 초기화 되고, 인형이 뽑힌 자리는 0으로 표시 된다.)
2) stack 최상단 인형과, 최상단 바로 아래 있는 인형이 같은지 비교한다.
3) 인형이 같을 경우 두 인형 모두 stack에서 삭제한다. 사라진 인형의 개수를 answer에 반영한다.

 

 

 

 

[코드의 문제점 & 개선점]

 

1. 인형을 무조건 stack에 넣은 다음 비교를 함.

  -> .push()와 .pop()을 한 번씩 더 수행하게 됨. 

   stack에 넣기 전에 stack의 최상단에 있는 인형과 비교를 했다면, 불필요하게 .push()와 .pop()을 수행하지 않아도 된다.

int tmp=board[i][pos-1];
board[i][pos-1]=0;
if(!stack.isEmpty() && tmp==stack.peek()){ //인형을 stack에 바로 넣지 않고, 최상단 인형과 비교
	answer+=2;
	stack.pop();
	}

 

 

2. stack이 비어있는지 확인하기 위해 stack.size()>1을 사용했다. 

-> !stack.isEmpty() 면 된다. 좀 더 직관적으로 표현이 가능했다.

 

 

3. 반복되는 코드

 while(y<n && board[y][x-1]==0){
     y++;
     if(y==n) break;
     }
 if(y==n) {
     y=0; //크레인 초기화
     continue;
     }

 

"크레인이 있는 위치가 0이면 크레인을 계속 내린다." 라는 생각으로 코드를 짰더니 위와 같은 지저분한 코드가 나왔다.

 

크레인이 2차원 배열의 영역을 벗어나지 않도록 하려다보니,  while 반복문을 탈출한 다음 continue를 사용해 for문의 처음으로 돌아가게 하는 괴상한 코드가 나왔다.

그리고 그 과정에서 조건을 걸어야하다보니 어쩔 수 없이 if(y==n)이 반복됐다.

 

 

"크레인을 계속내리다가 0이 아닌 곳에 도달하면 멈춘다." 라고 생각을 전환하면 아래와 같이 좀 더 깔끔하게 코드를 작성할 수 있다.

for(int y=0; y<board.length; y++){
	if(board[y][x-1]!=0){
		⁞(생략)
     }
}

 

 

+) y<n은 y<borad.length로 바꿀 수 있다.

   이렇게 하면 굳이 2차원 배열의 크기를 나타내는 변수n을 매개변수로 받지 않아도 된다.

 

++) 2차원 배열에서 배열명.length는 행(↓)의 길이를 나타낸다.

      열(→)의 길이를 나타내려면 배열명[0].length라고 하면 된다.

      (길이보다 개수라고 하면 좀 덜 헷갈릴지도)