[Week 6-1] ๐ฅํน๊ฐ 1์ผ์ฐจ
6์ฃผ์ฐจ ํ์์ผ
- ๊ฐ์ธ ๊ณต๋ถ
์ค๋๋ง์ ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ํ๊ธฐ~
[LeetCode 1380. Lucky Numbers in a Matrix]
์์์ ์ค๋ณต์ด ์๋ m x n
ํ๋ ฌ์ด ์ฃผ์ด์ง ๋ ํ๋ ฌ์ ์กด์ฌํ๋ ๋ชจ๋ Lucky number ๋ฅผ ๋ฐํํ๊ธฐ
Lucky number : ์์ ์ด ์ํ ํ์์๋ ์ต์๊ฐ์ด๋ฉฐ ์์ ์ด ์ํ ์ด์์๋ ์ต๋๊ฐ์ด ๋๋ ์์
-
์ ๊ทผ
๊ฐ ํ์์ ์ต์๊ฐ์ ์ฐพ์์ ์ต์๊ฐ์ด ์ํ ์ด์ ์ต๋๊ฐ๊ณผ ๋น๊ตํ๊ธฐ
์๊ฐ ๋ณต์ก๋ : O(m*n) = O(n^2) -
์ฝ๋
class Solution:
def luckyNumbers (self, matrix: List[List[int]]) -> List[int]:
# lucky number : ์์ ์ด ์ํ ํ์์๋ ์ต์, ์ด์์๋ ์ต๋๊ฐ ๋๋ ์
M = len(matrix[0])
N = len(matrix)
luckies = []
for row in matrix:
minNum = min(row)
minIdx = row.index(minNum)
col = [matrix[i][minIdx] for i in range(N)]
if max(col) == minNum:
luckies.append(minNum)
return luckies
- ๋ ๋น ๋ฅธ ๋ฐฉ๋ฒ์ ์์๊น?
์ถฉ๊ฒฉ
์์ฒญ๋๊ฒ ํ์ด์ฌ์ค๋ฌ์ด ์ฝ๋๋ฅผ ๋ฐ๊ฒฌํ๋ค. zip์ด๋ unpacking์ ์ด๋ป๊ฒ ์ฐ๋์ง ๋จธ๋ฆฌ๋ก๋ ์๊ณ ์๋๋ฐ ๋ฌธ์ ์ ์ ์ฉํ ์๊ฐ์ ๋ชป ํ๋ค... ํ์์์ ์ต์๊ฐ๊ณผ ์ด์์์ ์ต๋๊ฐ์ ๊ฐ๊ฐ ์ฐพ์์ ๊ต์งํฉ์ ๊ตฌํ๋ค๋ ๋ฐ์๋ ๋ชป ํ๋ค. ์์ง ๋ง๊ณ ๊ผญ ์จ๋จน์ด์ผ์ง.
์๊ฐ ๋ณต์ก๋ : O(N)? zip์ ์๊ฐ ๋ณต์ก๋๋ฅผ ์ ๋ชจ๋ฅด๊ฒ ๋ค.
ํ์ด์ฌ 3๋ถํฐ๋ zip์ด iterator ๊ฐ์ฒด ํํ๋ก ๋์ํ๊ธฐ ๋๋ฌธ์ zip์ ์๊ฐ ๋ณต์ก๋๊ฐ O(N)์ด๋ผ๊ณ ํ๋ค. ํ์ด์ฌ 2์์๋ zip์ด list๋ฅผ ๋ฐํํ๊ธฐ ๋๋ฌธ์ ์๊ฐ ๋ณต์ก๋๊ฐ O(N*M)์ด๋ค.
class Solution:
def luckyNumbers (self, matrix: List[List[int]]) -> List[int]:
# lucky number : ์์ ์ด ์ํ ํ์์๋ ์ต์, ์ด์์๋ ์ต๋๊ฐ ๋๋ ์
matrix_T = list(zip(*matrix))
rowMin = []
colMax = []
for row in matrix: # ๊ฐ ํ์์์ ์ต์๊ฐ
rowMin.append(min(row))
for col in matrix_T: # ๊ฐ ์ด์์์ ์ต๋๊ฐ
colMax.append(max(col))
return set(rowMin) & set(colMax)
Author And Source
์ด ๋ฌธ์ ์ ๊ดํ์ฌ([Week 6-1] ๐ฅํน๊ฐ 1์ผ์ฐจ), ์ฐ๋ฆฌ๋ ์ด๊ณณ์์ ๋ ๋ง์ ์๋ฃ๋ฅผ ๋ฐ๊ฒฌํ๊ณ ๋งํฌ๋ฅผ ํด๋ฆญํ์ฌ ๋ณด์๋ค https://velog.io/@zeen263/Week-6-1-ํน๊ฐ-1์ผ์ฐจ์ ์ ๊ท์: ์์์ ์ ๋ณด๊ฐ ์์์ URL์ ํฌํจ๋์ด ์์ผ๋ฉฐ ์ ์๊ถ์ ์์์ ์์ ์ ๋๋ค.
์ฐ์ํ ๊ฐ๋ฐ์ ์ฝํ ์ธ ๋ฐ๊ฒฌ์ ์ ๋ (Collection and Share based on the CC Protocol.)
์ข์ ์นํ์ด์ง ์ฆ๊ฒจ์ฐพ๊ธฐ
๊ฐ๋ฐ์ ์ฐ์ ์ฌ์ดํธ ์์ง
๊ฐ๋ฐ์๊ฐ ์์์ผ ํ ํ์ ์ฌ์ดํธ 100์ ์ถ์ฒ ์ฐ๋ฆฌ๋ ๋น์ ์ ์ํด 100๊ฐ์ ์์ฃผ ์ฌ์ฉํ๋ ๊ฐ๋ฐ์ ํ์ต ์ฌ์ดํธ๋ฅผ ์ ๋ฆฌํ์ต๋๋ค