프로그래머스 크레인 인형뽑기 게임; java

- 이진배열의 length는 행의 개수

 

import java.util.Stack;
 
public class Prog_1 {
    public static int solution(int[][] board, int[]moves) {
        int answer=0;
        //바구니
        Stack<Integer> stk=new Stack<>();
        
        //board에서 처음 인형이 있는 칸(맨 윗칸)을 기억한다. exist 배열에 저장
        int[] exist= new int[board.length];
        for(int i=0;i<board.length;i++) {//board의 c
            exist[i]=-1;    //exist 배열을 -1로 초기화
            for(int j=0;j<board.length;j++) {//board의 r
                if(board[j][i]==0) {//board i열을 위에서 아래까지 탐색
                    continue;        //인형이 없으면(0) 계속 탐색
                }else {                //인형이 있으면 위치(높이)를 저장하고 끝
                    exist[i]=j;
                    break;
                }
            }
        }
        /*
        System.out.print("exist 배열 : ");
        for(int i=0;i<board.length;i++) {
            System.out.print(exist[i]+" ");
        }
        System.out.println("");
        */
        
        //moves만큼 인형을 뽑는다.
        for(int i=0;i<moves.length;i++) {
            int c=moves[i]-1;
            int r=exist[c];
            int pick=-1;
            int prev=-1;
            //해당 열의 board에 인형이 있을 경우에만 인형을 뽑아 바구니에 넣는다.
            if(r>=0 && r<=board.length-1) {
                pick=board[r][c];
                if(!stk.isEmpty() && stk.peek()==pick) {//중복 인형일 경우
                    stk.pop();
                    answer=answer+2;
                }else {
                    stk.push(pick);
                }
                board[r][c]=0;
                exist[c]=exist[c]+1;
            }
            /*
            System.out.print("\n exist 배열 : ");
            for(int m=0;m<board.length;m++) {
                System.out.print(exist[m]+" ");
            }
            System.out.println("");
            */
        }
        
        return answer;
        
    }
    /*
    public static void main(String[] args) {
        int [][] board={{0,0,0,0,0},{0,0,0,0,0},{0,0,0,0,0},{0,0,0,0,0},{0,0,0,0,0}};
        int [] moves={1,5,3,5,1,2,1,4};
        int result=solution(board, moves);
        System.out.println(result);
    }
    */
 
}

위 코드는 이클립스에서 테스트할 때 코드

 

아래 코드는 프로그래머스 제출용 코드

import java.util.Stack;
class Solution {
    public static int solution(int[][] board, int[]moves) {
        int answer=0;
        //바구니
        Stack<Integer> stk=new Stack<>();
        
        //board에서 처음 인형이 있는 칸(맨 윗칸)을 기억한다. exist 배열에 저장
        int[] exist= new int[board.length];
        for(int i=0;i<board.length;i++) {//board의 c
            exist[i]=-1;    //exist 배열을 -1로 초기화
            for(int j=0;j<board.length;j++) {//board의 r
                if(board[j][i]==0) {//board i열을 위에서 아래까지 탐색
                    continue;        //인형이 없으면(0) 계속 탐색
                }else {                //인형이 있으면 위치(높이)를 저장하고 끝
                    exist[i]=j;
                    break;
                }
            }
        }
        
        //moves만큼 인형을 뽑는다.
        for(int i=0;i<moves.length;i++) {
            int c=moves[i]-1;
            int r=exist[c];
            int pick=-1;
            int prev=-1;
            //해당 열의 board에 인형이 있을 경우에만 인형을 뽑아 바구니에 넣는다.
            if(r>=0 && r<=board.length-1) {
                pick=board[r][c];
                if(!stk.isEmpty() && stk.peek()==pick) {//중복 인형일 경우
                    stk.pop();
                    answer=answer+2;
                }else {
                    stk.push(pick);
                }
                board[r][c]=0;
                exist[c]=exist[c]+1;
            }
        }
        return answer;
}
}

처음에 생각했을 때, 이중반복 피하려고 맨 위에 있는 인형을 먼저 찾아서 저장하는 방법을 택했다.

그런데 지금보니까 빅오는 똑같은거 같은데,, 심지어 더 걸리는 것 같다..... 

걍 포문 두번 돌리면서 탐색하는게 빠르네,,,,,,,,,,,,,,,,,,,,,,,

일단 답은 맞았으니까,,,,,,,,,,,,,,