๋ฌธ์ ์ค๋ช
1์ 0๋ก ์ฑ์์ง ํ(board)๊ฐ ์์ต๋๋ค. ํ 1์นธ์ 1 x 1 ์ ์ ์ฌ๊ฐํ์ผ๋ก ์ด๋ฃจ์ด์ ธ ์์ต๋๋ค. ํ์์ 1๋ก ์ด๋ฃจ์ด์ง ๊ฐ์ฅ ํฐ ์ ์ฌ๊ฐํ์ ์ฐพ์ ๋์ด๋ฅผ return ํ๋ solution ํจ์๋ฅผ ์์ฑํด ์ฃผ์ธ์. (๋จ, ์ ์ฌ๊ฐํ์ด๋ ์ถ์ ํํํ ์ ์ฌ๊ฐํ์ ๋งํฉ๋๋ค.)
์๋ฅผ ๋ค์ด
1 | 2 | 3 | 4 |
---|---|---|---|
0 | 1 | 1 | 1 |
1 | 1 | 1 | 1 |
0 | 0 | 1 | 0 |
๊ฐ ์๋ค๋ฉด ๊ฐ์ฅ ํฐ ์ ์ฌ๊ฐํ์
1 | 2 | 3 | 4 |
---|---|---|---|
0 | 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ํฉ๋๋ค.
๐๋ฌธ์ ํ์ด๐
def solution(board):
for i in range(1, len(board)): #height
for j in range(1, len(board[0])): #width
if board[i][j] > 0:
board[i][j] = min(board[i-1][j], board[i][j-1], board[i-1][j-1]) + 1 #์ต์๊ฐ + 1
#ํด๋น ์ขํ๊ฐ์ ์, ์, ๋๊ฐ์ ์์ ์ซ์ ์ค ์ต์๊ฐ์์ + 1 ์ฃผ๋ณ์ ๊ฐ์ ์ํด ์ ์ฌ๊ฐํ์ ํ์ธ
answer = []
for i in board:
for j in i:
answer.append(j)
return max(answer)**2
๋ค๋ฅธ ์ฌ๋ ํ์ด๐
def findLargestSquare(board):
answer = 1
res = [[1 if x=='O' else 0 for x in y] for y in board]
for y in range(len(board)):
for x in range(len(board[y])):
if board[y][x] == 'O':
res[y][x] = min(res[y-1][x], res[y-1][x-1], res[y][x-1]) + 1
if res[y][x] > answer: answer = res[y][x]
return answer ** 2