[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)
                

์ข‹์€ ์›นํŽ˜์ด์ง€ ์ฆ๊ฒจ์ฐพ๊ธฐ