빙고 개수 카운트하기

프로그래머스 모의테스트 마지막 문제였던 빙고 문제

솔직히 다른 알고리즘이 자신있는건 아니지만

현재 가장 자신없는 알고리즘 부분은 BFS/DFS.. 탐색!! 부분입니다.

그래서 문제로 다중 행렬 나온다음에 넓이 체크하라는거 나오면 솔직히 겁부터 나긴 합니다. 

탐색 알고리즘을 완전히 이해한 후 문제를 풀려고 했으나 

일단 그냥 풀어보고 싶은 알수없는 오기(?) 발동으로 빙고 문제를 풀어봤습니다.

막 풀어서 코드가 길어요..

그럼 풀어봅시다

[문제]

* 빙고는 NxN 크기의 게임 보드 칸에 1부터 NxN까지의 자연수를 중복 없이 하나씩 적은 후 숫자를 하나씩 지워나가는 게임입니다.

*  이때, 가로, 세로, 대각선 방향으로 한 줄에 적힌 숫자를 모두 지울 경우 빙고를 1개 만들었다고 합니다.

- 다음은 4X4 크기의 게임 보드를 이용해 게임을 진행한 예시입니다.

- 위와 같이 각 칸에 숫자가 적혀 있을 때, 위 게임 보드에서 순서대로 지운 숫자가 [14,3,2,4,13,1,16,11,5,15]인 경우 아래와 같이 빙고 3개가 만들어집니다.

빙고 게임 보드에 적힌 숫자가 담겨있는 배열 board, 게임 보드에서 순서대로 지운 숫자가 들어있는 배열 nums가 매개변수로 주어질 때,

board에서 nums에 들어있는 숫자를 모두 지우면 몇 개의 빙고가 만들어지는지 return하도록 solution함수를 완성해주세요.

[제한사항]

board는 게임 보드 칸에 적힌 숫자를 뜻하는 NxN크기의 2차원 배열이며, N은 2 이상 500이하의 자연수입니다.

board의 각 칸에는 1 이상 NxN이하의 자연수가 중복 없이 하나씩 들어있습니다.

nums는 board에서 지울 숫자가 들어있는 배열이며, 길이는 1 이상 NxN이하입니다.

nums에 들어있는 숫자는 1 이상 NxN이하의 자연수이며, 중복된 수가 들어있지 않습니다.

[문제 풀이]

저는 다음과 같은 순서로 문제를 풀었습니다.

1. num 배열에 있는 수를 하나씩 체크하며 보드 판에 해당 숫자가 있는지를 확인하고, 있으면 0으로 바꾸어 준다.

2. 바꾸어진 빙고판을 count_bingo() 함수로 보내어 빙고 갯수를 판별한다.

package pracitce_note;
 
public class mock_test03 {
    //빙고판 확인 함수
    public static int[][] confirm_borad(int[][] b,int num) {
        
        for(int i=0; i<b.length; i++) {
            for(int j=0; j<b.length; j++) { //숫자 있으면 0으로 변경
                if(b[i][j]==num) { 
                    b[i][j] = 0;
                }
            }
        }
        return b;
    }
    //디버깅용 출력 함수
    /*public static void print(int[][] b) {
        for(int i=0; i<b.length; i++) {
            for(int j=0; j<b.length; j++) {
                System.out.print(b[i][j]+" ");
            }
            System.out.println();
        }
    }*/
    //빙고 카운트
    public static void count_bingo(int[][] board) {
        
        //가로와 세로를 체크해 줄 V - H 배열 생성
        int v[] = new int[board.length];
        int h[] = new int[board.length];
        int c[] = new int[2]; //대각선은 두개 뿐 
        int count =0;
        //0으로 바뀐거 체크하면서 가로 / 세로/ 대각선 체크
            for(int i=0; i<board.length; i++) {
                for(int j=0; j<board.length; j++) {
                    //가로 카운트
                    if(board[i][j]==0) {
                        v[i]++; //가로 체크
                        h[j]++; //세로 체크
                        if(i==j) { //대각선 체크
                            c[0]++;
                        }
                        if(i+j==board.length-1) {
                            c[1]++;
                        }
                    }
                }
            }
        //체크값 확인해서 빙고면 count++    
        for(int k=0; k<v.length; k++) {    
             if(v[k] == v.length) {
                 count++;
             }
             if(h[k] == v.length) {
                 count++;
             }
        }
        //대각선은 어떤 빙고판이든 2개라서.. 따로 빼서 체크..
         if(c[0]==v.length) {
             count++;
         }
         if(c[1]==v.length) {
             count++;
         }
         //count 값
         System.out.println(count);
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        
        int[][] board = {{11,13,15,16},{12,1,4,3},{10,2,7,8},{5,14,6,9}};
        int[] num = {14,3,2,4,13,1,16,11,5,15};
        
        /* solution
         * 1. num에 있는 숫자를  하나씩 비교하며 board에 있는경우 0으로 바꾼다
         * 2. 바꾸어진 board에 빙고 부분을 카운트 한다.
         * */
        //num 하나씩 보내면서 체크하기
        for(int i=0; i<num.length; i++) {
            confirm_borad(board,num[i]);
        }
        //print(board);
        
        count_bingo(board); //빙고 체크하기
 
    }
 
}
 

효율성은 O(2n^2)? 되는거같은뎅 

풀고보니 num 체크하면서 바로바로 카운트하면 함수를 두개로 나눌 필요가 없어보이긴 합니다

근거없는 자신감이지만 탐색 알고리즘을 공부하고나면 코드가 엄청 줄고 효울성도 올라갈 것 같은 기분이 ㅋㅋ

빨리 탐색 알고리즘 공부를 해야겠네요