강의로 돌아가기
맛탱

질문이 있습니다.

강좌를 듣고 JAVA로 풀어보았는데요. 잘 이해가 되지 않아서, 그냥 강좌데로 풀어서 작성해 보았는데 정확성 테스트와 효율성 테스트 둘 다 불합격으로 뜹니다.

    private static int solution(int[][] board) {
        int answer = 0;
        int row = board.length;
        int col = board[0].length;
        int[][] dp = new int[1001][1001];
        System.out.println(row+"/"+col);
        for(int i=1; i<=row; i++)
            for(int j=1; j<=col; j++) {
                try {
                    if(board[i][j]!=0) {
                        dp[i][j] = Math.min(board[i][j-1], Math.min(board[i-1][j], board[i-1][j-1]))+1;
                    }
                    answer = Math.max(answer,  dp[i][j]);
                }catch(ArrayIndexOutOfBoundsException e) {

                }
            }
        return answer*answer;
    }

그래서 직접 풀어보았지만, 정확성은 모두 통과하였는데 효율성은 모두 불합격이 나왔어요.
ㅡ,.ㅡ 이 문제 정말 어렵네요

작성중인 코드―Solution.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
class Solution
{
    private static int[][] source = null;
    private static int row = 0;
    private static int col = 0;
    private static int min = 0;
    private static int max = 0;
    private static int tryCnt = 0;

    //동영상강좌가 이해도 안갔고, 동영상강좌의 내용도 코드채점에 실패하여 직접 작성한다.
    public static int solution(int[][] board) {
        if(board.length>1000) return 0;
        for(int i=0, il=board.length; i<il; i++) {
            if(board[i].length>1000) return 0;
        }
        source = board;
        int answer = 0;
        //1.필요한 정보
        row = source.length; //입력받은 가로 크기
        col = source[0].length; //입력받은 세로 크기
        min = Math.min(row, col); //입력받은 값 중 가장 작은 크기
        max = Math.max(row, col); //입력받은 값 중 가장 큰 크기
        tryCnt = 0; //시도횟수(제일큰(min)것 부터 min-tryCnt로 찾아나감)
        //System.out.println();
        //2. 제일큰 정사각형(min)에서부터 제일 작은 정사각형(min-tryCnt)까지 계산한다.
        while(max-tryCnt>0) {
            //System.out.println("min = "+ min +", max = "+ max +", min-tryCnt = "+ (min-tryCnt));
            /*결과값: 9
                0   1   1   1
                1   1   1   1
                1   1   1   1
                0   0   1   0
            */
            /*결과값: 4
                0   0   1   1
                1   1   1   1           
            */
            /*결과값: 4
                0   1   1   1
                1   1   1
                1   1   1   0           
            */
            //System.out.println(min +" - "+ tryCnt +" = "+ (min-tryCnt));
            for(int i=0, il=row-min+tryCnt; i<=il; i++) {//가로
                for(int j=0, jl=col-min+tryCnt; j<=jl; j++) {//세로
                    //System.out.print("    "+ i +" - "+ j +" >> "+ (min-tryCnt));
                    //2. 정사각형 넓이에 모두 1인지 체크(true: 모두1, false:!모두1)
                    boolean result = test(i, j, min-tryCnt);
                    //System.out.println("  >> "+ result +"("+ (min-tryCnt) +")");
                    if(result) {
                        answer = min-tryCnt;
                        return answer*answer;
                    }
                }
            }
            tryCnt++;
        }


        return answer*answer;
    }

    //2. 정사각형 넓이에 모두 1인지 체크(true: 모두1, false:!모두1)
    private static boolean test(int r, int c, int size){ //r:세로출발점, c:가로출발점, size:정사각형 한변 넓이
        for(int i=r, il=r+size; i<il && i<row; i++) {//가로
            for(int j=c, jl=c+size; j<jl && j<col; j++) {//세로
                try {
                    //System.out.print(" > "+ source[i][j]);
                    if(source[i][j]==0) return false;
                }catch(ArrayIndexOutOfBoundsException e) {
                    //System.out.print(" > ArrayIndexOutOfBoundsException");
                    return false;
                }
            }
        }
        return true;    
    }
}
0 개의 답변
답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.