프로그래머스 레벨1 - 공원[자바]

문제

 

프로그래머스

 

풀이

 

mats 가 정사각형이기 때문에 2차원 배열을 탐색하면서 -1인 값을 찾고 그곳을 시작점으로 정사각형의 넓이만큼 -1이 존재하는지를 조건문으로 검색합니다.

 

class Solution {
    public int solution(int[] mats, String[][] park) {
        for(int m : mats) {
          for(int i=0; i<park.length; i++) {
            for(int j=0; j<park[i].length; j++) {
                if(park[i][j].equals("-1")) {
                    if(matchSquare(i, j, m, park)) {
                      return m;  
                    } 
                }
            }
          }  
        }
        
        return -1;
    }
    
    private boolean matchSquare(int x, int y, int answer, String[][] park) {
       for(int i=0; i<answer; i++) {
            for(int j=0; j<answer; j++) {
                if(x+answer-1 < park.length && y+answer-1 < park[x].length) {
                    String s = park[x+i][y+j];
                    if(!s.equals("-1")) return false;    
                } else {
                    return false;
                }   
            }
        } 
        
        return true;
    }
}

 

mats 배열의 원소를 하나씩 꺼내서 하나씩 비교합니다. 30점 나왔습니다.

뭐가 문제인지 문제부터 다시 읽었는데 mats의 배열의 원소가 정렬되지 않은 상태였습니다. 그래서 최대값을 구해야하는 답과는 틀린 결과가 나왔습니다.

 

그래서 mats를 내림차순으로 정렬시켜 주었습니다.

 

...
mats = Arrays.stream(mats)
            .boxed()
            .sorted(Collections.reverseOrder())
            .mapToInt(Integer::intValue)
            .toArray();
...

 

정렬은 스트림함수를 사용하여 Integer형으로 변환 후 내림차순으로 정렬시켜 준 다음에 다시 int형으로 바꿔주었습니다. 이렇게 하니까 정답이 나왔습니다. 하지만 당연히 성능이 별로 안좋았습니다. 정렬은 정렬대로 하고 for문도 for문대로 돌았으니 당연한 것 같습니다.

 

리팩토링

 

돗자리를 펼 수 있는지 확인하는 메소드인 matchSquare() 에서 배열의 끝을 넘어가는지 확인하는 조건문의 위치를 수정해주었습니다.

 

private boolean matchSquare(int x, int y, int answer, String[][] park) {
	// 조건문을 밖으로 뺌
   if(x+answer-1 >= park.length || y+answer-1 >= park[x].length) return false;

   for(int i=0; i<answer; i++) {
        for(int j=0; j<answer; j++) {
            String s = park[x+i][y+j];
            if(!s.equals("-1")) return false;    
        }
    } 

    return true;
}

 

그리고 정렬을 시켜주었던 로직 대신 answer 변수를 추가하여 Math.max() 함수를 이용하여 answer와 for문을 돌며 구한 값을 비교하여 최대값이 저장되도록 바꿔주었습니다.

 

...
int answer = -1;
        
for(int m : mats) {
  for(int i=0; i<park.length; i++) {
    for(int j=0; j<park[i].length; j++) {
        if(park[i][j].equals("-1")) {
            if(matchSquare(i, j, m, park)) {
              answer = Math.max(answer, m);  
            } 
        }
    }
  }  
}

return answer;
...

 

그래서 다음 최종 답이 나왔습니다.

 

import java.util.*;
class Solution {
    public int solution(int[] mats, String[][] park) {
        int answer = -1;
        
        for(int m : mats) {
          for(int i=0; i<park.length; i++) {
            for(int j=0; j<park[i].length; j++) {
                if(park[i][j].equals("-1")) {
                    if(matchSquare(i, j, m, park)) {
                      answer = Math.max(answer, m);  
                    } 
                }
            }
          }  
        }
        
        return answer;
    }
    
    private boolean matchSquare(int x, int y, int answer, String[][] park) {
       if(x+answer-1 >= park.length || y+answer-1 >= park[x].length) return false;
        
       for(int i=0; i<answer; i++) {
            for(int j=0; j<answer; j++) {
                String s = park[x+i][y+j];
                if(!s.equals("-1")) return false;    
            }
        } 
        
        return true;
    }
}

 

 

 

다음과 같이 시간이 개선되었습니다.