문제 주소
https://school.programmers.co.kr/learn/courses/30/lessons/12905
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제 설명
1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)
예를 들어
1 2 3 4
| 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 |
| 0 | 0 | 1 | 0 |
가 있다면 가장 큰 정사각형은
1 2 3 4
| 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 |
| 0 | 0 | 1 | 0 |
가 되며 넓이는 9가 되므로 9를 반환해 주면 됩니다.
제한사항
- 표(board)는 2차원 배열로 주어집니다.
- 표(board)의 행(row)의 크기 : 1,000 이하의 자연수
- 표(board)의 열(column)의 크기 : 1,000 이하의 자연수
- 표(board)의 값은 1또는 0으로만 이루어져 있습니다.
입출력 예
board answer
| [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] | 9 |
| [[0,0,1,1],[1,1,1,1]] | 4 |
입출력 예 설명
입출력 예 #1
위의 예시와 같습니다.
입출력 예 #2
| 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 |
로 가장 큰 정사각형의 넓이는 4가 되므로 4를 return합니다.
제출 코드
import java.lang.Math;
class Solution
{
public int solution(int [][] board)
{
int [][] ones = new int [board.length][board[0].length];
int maxStreak = 0;
if(board.length==1){
return board[0][0];
}
// 행 초기세팅
for(int i=0; i<board.length; i++){
ones[i][0] = board[i][0];
}
//열 초기세팅
for(int j=0; j<board[0].length; j++){
ones[0][j] = board[0][j];
}
for (int i = 1; i < board.length; i++) {
for (int j = 1; j < board[0].length; j++) {
if (board[i][j] == 1) {
ones[i][j] = Math.min(Math.min(ones[i-1][j], ones[i][j-1]), ones[i-1][j-1]) + 1;
maxStreak = Math.max(maxStreak, ones[i][j]);
}
}
}
return maxStreak*maxStreak;
}
}코드 설명
dp를 사용해서 풀었다
풀어볼만한 좋은 문제였던 것 같다!
풀이 과정
효율적인 풀이를 찾기 위해서 시행착오를 거쳤다.
첫번째같이 하급 풀이를 해내니까 잘 풀었다고 생각하고 다 풀어서 내도 코테에서 떨어지는 것 같다!
내공을 더 쌓아야겠다는 생각을 했다
첫번째 풀이
import java.lang.Math;
class Solution
{
int [][] arr;
int [][][] ones;
public int solution(int [][]board)
{
arr = board;
ones = new int [board.length][board[0].length][2];
int maxSize = 0;
//어떤 칸부터 아래 1 개수 세고.. 오른쪽 1 개수 세고..? 써놨다가 그것만 보면서 계산하기?
//그것만 본다면 아래 위 개수 세어가지고 아래, 위 중의 더 작은것의 max를 구해놓으면 될듯
for(int i=0; i<board.length; i++){
for(int j=0; j<board[0].length; j++){
if(arr[i][j]==1){
int [] result = ones[i][j];
result[0] = count(i,j,1,0,1);//down
result[1] = count(i,j,1,1,0);//right
}
}
}
for(int i=0; i<ones.length; i++){
for(int j=0; j<ones[0].length; j++){
int [] result = ones[i][j];
maxSize = Math.max(maxSize,Math.min(result[0],result[1]));
}
}
return maxSize*maxSize;
}
int count(int x, int y, int count, int xWay, int yWay){
int X = x+xWay;
int Y = y+yWay;
if(X<arr.length && Y<arr[0].length){
count = count(X,Y,count+1,xWay,yWay);
}
return count;
}
}어떤 칸부터 아래쪽으로 가면서 1의 개수를 세어서 ones[i][j][0]에 적어둔다
어떤 칸부터 오른쪽으로 가면서 1의 개수를 세어서 ones[i][j][1]에 적어둔다
다 적은 후에 그 칸의 ones[i][j][0]과 ones[i][j][1]을 비교해서 둘 중 작은 것을 골라서 maxSize에 넣는다(지금보니까 비교 방식도 잘못되었음, 한 줄씩만 보는데 오른쪽으로 1으로 체크된 모든 칸에서부터 밑으로의 size와 비교해서 가장 작은거 골랐었어야 함)
테스트 1
입력값 〉 [[0, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1], [0, 0, 1, 0]]
기댓값 〉 9
실행 결과 〉 테스트를 통과하였습니다.
테스트 2
입력값 〉 [[0, 0, 1, 1], [1, 1, 1, 1]]
기댓값 〉 4
실행 결과 〉 테스트를 통과하였습니다.어찌되었든 테스트는 돌아가길래 신나서 제출했다
정확성 테스트
테스트 1 〉 통과 (0.05ms, 74.6MB)
테스트 2 〉 실패 (0.14ms, 76MB)
테스트 3 〉 통과 (0.14ms, 77MB)
테스트 4 〉 실패 (0.22ms, 69.8MB)
테스트 5 〉 통과 (0.19ms, 74MB)
테스트 6 〉 실패 (0.08ms, 79.7MB)
테스트 7 〉 실패 (0.05ms, 75.9MB)
테스트 8 〉 통과 (0.09ms, 78.6MB)
테스트 9 〉 실패 (0.10ms, 75.2MB)
테스트 10 〉 실패 (0.14ms, 70.8MB)
테스트 11 〉 통과 (0.06ms, 77.2MB)
테스트 12 〉 실패 (0.12ms, 75.4MB)
테스트 13 〉 실패 (0.06ms, 77.4MB)
테스트 14 〉 실패 (0.16ms, 81.9MB)
테스트 15 〉 실패 (0.19ms, 75.1MB)
테스트 16 〉 실패 (0.15ms, 74.5MB)
테스트 17 〉 실패 (0.14ms, 75.8MB)
테스트 18 〉 실패 (2.08ms, 77.7MB)
테스트 19 〉 실패 (2.03ms, 73.1MB)
효율성 테스트
테스트 1 〉 실패 (시간 초과)
테스트 2 〉 실패 (시간 초과)
테스트 3 〉 실패 (시간 초과)틀리는것도 틀리는 거지만 시간 초과가 나서 근본적으로 잘못된 접근방식이라고 생각하게 되었다
두번째 풀이
매번 또 세지 말고 dp마냥 업데이트를 하는게 낫지 않을까… 싶어서 dp를 나름 도입해봄
import java.lang.Math;
class Solution
{
int [][] arr;
int [][][] ones;
public int solution(int [][]board)
{
arr = board;
ones = new int [board.length][board[0].length][2];
int maxSize = 0;
//count down
for(int j=0; j<board[0].length; j++){
int continuous = 0;
for(int i=0; i<board.length; i++){
if(arr[i][j]==0){
continuous = 0;
}else{
int [] result = ones[i][j];
continuous++;
result[0] = continuous;//down
}
}
}
//count right
for(int i=0; i<board.length; i++){
int continuous = 0;
for(int j=0; j<board[0].length; j++){
if(arr[i][j]==0){
continuous = 0;
}else{
int [] result = ones[i][j];
continuous++;
result[1] = continuous;//right
}
}
}
for(int i=0; i<ones.length; i++){
for(int j=0; j<ones[0].length; j++){
int [] result = ones[i][j];
maxSize = Math.max(maxSize,Math.min(result[0],result[1]));
}
}
return maxSize*maxSize;
}
}이번에는 한 열, 한 행씩 세면서 1이 증가한 범위를 넣어줌 0이 나온다면 초기화함
테스트 1 〉 통과 (0.04ms, 80.6MB)
테스트 2 〉 통과 (0.10ms, 78.6MB)
테스트 3 〉 통과 (0.05ms, 73.7MB)
테스트 4 〉 통과 (0.09ms, 75.6MB)
테스트 5 〉 통과 (0.05ms, 76.2MB)
테스트 6 〉 실패 (0.05ms, 78.7MB)
테스트 7 〉 통과 (0.06ms, 74.1MB)
테스트 8 〉 통과 (0.10ms, 76.9MB)
테스트 9 〉 통과 (0.05ms, 70.9MB)
테스트 10 〉 통과 (0.05ms, 78.2MB)
테스트 11 〉 실패 (0.07ms, 71.3MB)
테스트 12 〉 실패 (0.08ms, 69.6MB)
테스트 13 〉 실패 (0.04ms, 71.8MB)
테스트 14 〉 실패 (0.08ms, 77.3MB)
테스트 15 〉 실패 (0.12ms, 72.5MB)
테스트 16 〉 실패 (0.12ms, 78.6MB)
테스트 17 〉 실패 (0.06ms, 72.9MB)
테스트 18 〉 실패 (0.47ms, 71.2MB)
테스트 19 〉 실패 (0.45ms, 70.9MB)
효율성 테스트
테스트 1 〉 실패 (시간 초과)
테스트 2 〉 실패 (시간 초과)
테스트 3 〉 실패 (시간 초과)이것도 위와 마찬가지로 한 줄씩만 봐서 틀린 풀이이다
그리고 for문 3번이 너무 헤비해서 시간 초과가 났다
세번째 풀이
for문을 하나로 줄일수 있을까 생각해봄
import java.lang.Math;
class Solution
{
public int solution(int [][]board)
{
int [][] ones = new int [board.length][board[0].length];
int maxStreak = 0;
// 행 초기세팅
for(int i=0; i<board.length; i++){
ones[i][0] = board[i][0];//으아악 으아악 for문 하나로 어떻게 합쵸ㅕ
}
//열 초기세팅
for(int j=0; j<board[0].length; j++){
ones[0][j] = board[0][j];
}
for (int i = 1; i < board.length; i++) {
for (int j = 1; j < board[0].length; j++) {
if (board[i][j] == 1) {
ones[i][j] = Math.min(Math.min(ones[i-1][j], ones[i][j-1]), ones[i-1][j-1]) + 1;
maxStreak = Math.max(maxStreak, ones[i][j]);
}
}
}
return maxStreak*maxStreak;
}
}첫 행과 첫 열의 값을 .dp에 넣어준다
그리고 이중 for문을 한 번만 돌면서
그 자리가 1이면
ones[i][j] = Math.min(Math.min(ones[i-1][j], ones[i][j-1]), ones[i-1][j-1]) + 1;
-> ones[i-1][j] , ones[i][j-1] , ones[i-1][j-1] 중의 가장 작은것에 +1 한다
| ones[i-1][j-1] | ones[i-1][j] |
| ones[i][j-1] | ones[i][j] |
색칠된 칸 중에서 값이 제일 작은 것에 +1을 해준다 == 가장 작은 정사각형을 확장한다
maxStreak = Math.max(maxStreak, ones[i][j]); 그리고 maxStreak에 가장 큰 값을 저장한다!
그것의 제곱이 사이즈가 된다!
'Coding Test' 카테고리의 다른 글
| [백준] 이전 순열 (0) | 2024.06.21 |
|---|---|
| [백준] 다음 순열 (0) | 2024.06.21 |
| [백준] 크게 만들기 (0) | 2024.06.16 |
| [프로그래머스] 124나라의 숫자 (0) | 2024.06.03 |
| [프로그래머스] 파일명 정렬 (1) | 2024.06.03 |
