문제 출처

코딩테스트 연습 > 공원
https://school.programmers.co.kr/learn/courses/30/lessons/340198

문제 설명

사람들이 돗자린 핀 상태를 나타내는 2차원 배열 park, 지민이가 가진 돗자리 한 변의 길이가 담긴 정수 리스트 mats가 있을 때, 지민이가 깔 수 있는 가장 큰 돗자리 한 변의 길이를 return 하라.

접근 방법

간단하게 for문을 이용하여 각 돗자리 한 변의 길이를 가지고 있는 정사각형을 park에 한 번씩 대보고, 칸을 계속 이동하는 방식이다.

단, 한 칸이라도 사람이 있는 곳을 대면 해당 위치는 아예 사용하지 못하므로 break를 통해 for문을 빠져나온다.

import java.util.*;

class Solution {
    public int solution(int[] mats, String[][] park) {
        int rows = park.length;
        int cols = park[0].length;
        int maxSize = -1;
        
        Arrays.sort(mats);
        
        for (int m = mats.length - 1; m>= 0; m--){
            boolean canPlace = false;
            
            for (int i = 0; i<=rows - mats[m]; i++){
                for (int j = 0; j<= cols - mats[m]; j++){
                    boolean allMinusOne = true;
                    
                    for (int x = i; x<i +mats[m]; x++){
                        for(int y = j; y<j+mats[m]; y++){
                            if(!park[x][y].equals("-1")){
                                allMinusOne = false;
                                break;
                            }
                        }
                        if(!allMinusOne) break;
                    }
                    if(allMinusOne){
                        canPlace = true;
                        break;
                    }
                }
                if (canPlace) break;
            }
            if(canPlace){
                maxSize = mats[m];
                break;
            }
        }
        return maxSize;
    }
}

출처
https://school.programmers.co.kr/questions/80567?referer=collection-of-questions

Review

import java.util.*;

class Solution {
    public int solution(int[] mats, String[][] park) {
        int answer = -1;
        
        Arrays.sort(mats);
        
        for(int i = 0; i<mats.length/2; i++){
            int temp = mats[i];
            mats[i] = mats[mats.length-1-i];
            mats[mats.length-1-i] = temp;
        }
        
        for(int k : mats){
            
            for(int i = 0; i<=park.length-k; i++){
                for(int j = 0; j<=park[0].length-k; j++){
                    boolean putMats = true;
                    
                    for(int m = i; m<i+k; m++){
                        boolean allMinus = true;
                        for(int n = j; n<j+k; n++){
                            if(!park[m][n].equals("-1")){
                                allMinus = false;
                                break;
                            }
                        }
                        if(!allMinus){
                            putMats = false;
                            break;
                        }
                    }
                    if(putMats) return k;
                }
            }
        }
        
        return answer;
    }
}

알게된 점

처음 내가 풀었던 풀이이다. 하지만 틀렸다.
다른 사람이 푼 풀이(풀이 방법 코드)와 비교해도 로직은 똑같으나 틀렸다.
그 이유는 정렬의 방식 때문이였다.
int[] arrangeMats = mats는 같은 배열을 참조하기 때문에 정렬하는 식이 통하지 않은 것이다.
Review 하면서 정렬 방식을 바꿔야겠다. (Stream 공부도 같이 하면 좋겠다.)

import java.util.*;

class Solution {
    public int solution(int[] mats, String[][] park) {
        int answer = -1;
        
        Arrays.sort(mats);
        int o = mats.length-1;
        int[] arrangeMats = mats;
        for(int i = 0; i<mats.length; i++){
            mats[i] = arrangeMats[o--];
        }
        
        
        for(int k : mats){
            boolean putMats = false;
            
            for(int m = 0; m<=park.length-k; m++){
                for(int n = 0; n<=park[1].length-k; n++){
                    boolean checkMinus = true;
                    
                    for(int i = m; i<m+k; i++){
                        for(int j = n; j<n+k; j++){
                            if(!park[i][j].equals("-1")){
                                checkMinus = false;
                                break;
                            }
                        }
                        if(!checkMinus) break;
                    }
                    
                    if(checkMinus){
                        putMats = true;
                        break;
                    }
                }
                if(putMats) return k;
            }
        }
    
        return answer;
    }
}

Review
풀면서 한 번 헷깔린 것은 Review 풀이의 i,j의 종료 조건을 정하는 것이였다. 정사각형 돗자리를 놓을 수 있는 시작 인덱스를 찾는 것이므로, '<'가 아닌 '<='가 되어야 한다. (사실 잘 모르겠으면, 그림에 직접 갯수를 세어보면 편하다.)

문제푼 흔적

Review