[Algorithm] 6월 17일 알고리즘 연습 (프로그래머스 LEVEL2) - 에이젠

Lv. 2 쿼드압축 후 개수 세기 - 실패

 

참고한 풀이

https://devdange.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%BF%BC%EB%93%9C%EC%95%95%EC%B6%95-%ED%9B%84-%EA%B0%9C%EC%88%98-%EC%84%B8%EA%B8%B0-for-JAVA-%EB%B6%84%ED%95%A0%EC%A0%95%EB%B3%B5

[프로그래머스] 쿼드압축 후 개수 세기 for JAVA 분할정복

 

 

Lv. 2 스킬트리 - 실패 

참고한 풀이

https://mozzioi.tistory.com/99

[프로그래머스] [Java] 스킬트리

 

Lv. 2 방문 길이 - 실패

참고한 풀이

https://ilmiodiario.tistory.com/97

[프로그래머스] level2. 방문 길이 (자바 JAVA)

 

Lv. 2 가장 큰 정사각형 찾기 - 실패

첫번째 풀이(1) : 효율성 테스트를 통과하지 못함.

class Solution
{
    public int solution(int [][]board)
    {
        int answer = 0;

        for(int i = 0 ; i < board.length; i++){
            for(int j = 0 ; j < board[i].length ; j++){
                int range = check(i,j,board);
                int result = findSqure(i, j, range, board);
                if(result == 1) {
                    answer = Math.max(answer, range);
                }
            }
        }

        answer = answer * answer;
        return answer;
    }
    
    public int check(int row, int col, int[][] arr){
        int candX = 1;
        int candY = 1;
        for(int i = row; i < arr.length - 1; i++){
            if(arr[i][col] == arr[i + 1][col]){
                candY++;
            }else{
                break; //같지 않은경우 개수세기 종료
            }
        }
        for(int j = col ; j < arr[0].length - 1; j++){
            if(arr[row][j] == arr[row][j+1]){
                candX++;
            }else{
                break; //같지 않은경우 개수세기 종료
            }
        }
        return Math.min(candX,candY);
    }
    
    public int findSqure(int startX, int startY,int range, int[][] arr){
        for(int i = startX ; i < startX + range ; i++){
            for(int j = startY ; j < startY + range ; j++){
                if(arr[i][j] == 0){
                    return -1;
                }
            }
        }
        return 1;
    }
    
}

 

참고한 풀이

class Solution
{
    public int solution(int [][]board)
    {
        int answer = 1;

        int r = board.length;
        int c = board[0].length;
        
        //표가 전부 0으로 이루어진지 확인
        int zero = 0;
        for(int i=0; i<r; i++){
            for(int j=0; j<c; j++){
                if(board[i][j] == 1)
                    break;
                zero++;
            }
        }
        //모두 0인 경우
        if(zero == r*c)
            return 0;
        
        //가장 큰 정사각형 구하기
        for(int i=1; i<r; i++){
            for(int j=1; j<c; j++){
                if(board[i][j] == 0)
                    continue;
                board[i][j] = Math.min(Math.min(board[i-1][j],board[i][j-1]), board[i-1][j-1])+1;
                if(board[i][j] > answer)
                    answer = board[i][j];
            }
        }
        
        //넓이
        answer = answer*answer;

        return answer;
    }
}

https://excited-hyun.tistory.com/205

[프로그래머스 - Java] 가장 큰 정사각형 찾기