Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- MySQL
- Spring
- 파이썬
- 백준 17779
- 백준 16235
- springboot
- 프로래머스
- spring oauth
- JVM
- java 기술면접
- MSA
- 웹어플리케이션 서버
- re.split
- spring security
- 백준 17626
- 백준 16719
- spring cloud
- with recursive
- 프로그래머스
- Spring Boot
- JPA
- 백준 19238
- Coroutine
- 백준 16236
- 백준 15685
- 백준 파이썬
- sql 기술면접
- 백준
- java
- Kotlin
Archives
- Today
- Total
시작이 반
[프로그래머스] 가장 큰 정사각형 찾기(Java 자바) 본문
SMALL
https://programmers.co.kr/learn/courses/30/lessons/12905#
문제 설명
1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)
예를 들어
12341 | 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합니다.
class Solution
{
public int solution(int [][]board)
{
int answer = 0;
int[][] dp = new int[board.length][board[0].length];
for(int i = 0; i < board.length; i++){
for(int j = 0; j < board[0].length; j++){
dp[i][j] = board[i][j];
if(board[i][j] == 1){
answer = 1;
}
}
}
for(int i = 1; i < dp.length; i++){
for(int j = 1; j < dp[0].length; j++){
if(dp[i][j] != 0){
dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]) , dp[i-1][j-1]) + 1;
answer = Math.max(answer, dp[i][j] * dp[i][j]);
}
}
}
return answer;
}
}
핵심 코드, 푸는법:
dp문제이다. 2차원배열을 만들어서 i, j값을 구해준다.
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
LIST
'알고리즘 > Programmers' 카테고리의 다른 글
[프로그래머스] 파일명 정렬(Java 자바) (0) | 2021.12.19 |
---|---|
[프로그래머스] 압축(Java 자바) (0) | 2021.12.18 |
[프로그래머스] 방금그곡(Java 자바) (0) | 2021.11.15 |
[프로그래머스] 방문 길이(Java 자바) (0) | 2021.11.03 |
[프로그래머스] 스킬트리(Java 자바) (0) | 2021.11.02 |