[leetCode] 2133. Check if Every Row and Column Contains All Numbers (Python) (feat.ChatGPT)

코딩 1일 1문제 오늘의 문제는 leetCode 의 Check if Every Row and Column Contains All Numbers 입니다.

Check if Every Row and Column Contains All Numbers - LeetCode

👨🏻‍💻 문제 풀이

이중 반복문을 돌면서 각 행 / 열 이 1부터 각 행의 행/열의 길이인 n 까지의 숫자가 들어있는지 체크하고

맞지 않는 경우 반복문을 중단하고 정답을 False 를 return 하도록 하였습니다.

👨🏻‍💻 코드 ( Solution ) - SOMJANG

class Solution:
    def checkValid(self, matrix: List[List[int]]) -> bool:
        n = len(matrix)

        answer = True

        for row in range(n):
            if len(set(matrix[row])) != n:
                answer = False
                break
            temp = []
            for col in range(n):
                temp.append(matrix[col][row])
                
            if len(set(temp)) != n:
                answer = False
                break

        return answer

입력 받은 matrix 의 행, 열 길이를 먼저 구한 뒤

n = len(matrix)

n x n 만큼 도는 이중 반복문을 만들어 줍니다.

이중 반복문에서 첫번째 반복문에서는 행이 valid 한지 체크하고

두번째 반복문에서는 temp 리스트에 각 행의 row 번째 값을 모두 temp 리스트에다가 append 해주고

이렇게 만들어진 temp 리스트가 또 valid 한지 체크하도록 했습니다.

n = len(matrix)

answer = True

for row in range(n):
    if len(set(matrix[row])) != n:
        answer = False
        break
    temp = []
    for col in range(n):
        temp.append(matrix[col][row])

    if len(set(temp)) != n:
        answer = False
        break

👨🏻‍💻 코드 ( Solution ) - SOMJANG - set 으로 하면 더 좋을까?

class Solution:
    def checkValid(self, matrix: List[List[int]]) -> bool:
        n = len(matrix)

        answer = True

        for row in range(n):
            if len(set(matrix[row])) != n:
                answer = False
                break
            temp = set()
            for col in range(n):
                temp.add(matrix[col][row])
                
            if len(temp) != n:
                answer = False
                break

        return answer

첫번째 풀이처럼 풀고 생각해보니 temp 리스트에 모든 행의 row 번째 값을 append 한 뒤 

이를 다시 set -> len 하는게 좀 비효율 적인 것 같아 set add 가 더 빠르지 않을까? 라는 생각을 가지고 

list -> append 하던 것만 set -> add 로 바꾸어보았습니다.

* ChatGPT 에게 물어본 list append 와 set add 의 성능

일반적으로, list.append()보다 set.add()가 더 빠릅니다. 
이는 list.append()가 더 많은 작업을 수행해야 하기 때문입니다. 
list.append()는 리스트 끝에 항목을 추가하기 위해 리스트의 크기를 늘리고 할당된 메모리의 크기를 증가시켜야 합니다. 
반면에 set.add()는 해시 테이블에서 바로 추가 작업을 수행하므로 더 빠릅니다.

결과는! 조금 더 빠른 속도, 조금 더 적은 메모리를 사용하는 코드가 되었습니다.

👨🏻‍💻 코드 ( Solution ) - ChatGPT - 1회차 

class Solution:
    def checkValid(self, matrix: List[List[int]]) -> bool:
        n = len(matrix)
        for i in range(n):
            row_set = set(matrix[i])
            col_set = set(matrix[j][i] for j in range(n))
            if len(row_set) != n or len(col_set) != n:
                return False
            if row_set != col_set:
                return False
        return True

👨🏻‍💻 코드 ( Solution ) - ChatGPT - 2회차 - 더 빠르고 메모리를 덜 사용하는 코드를 부탁해

class Solution:
    def checkValid(self, matrix: List[List[int]]) -> bool:
        n = len(matrix)
        nums = set(range(1, n+1))
        for i in range(n):
            row_set = set(matrix[i])
            col_set = set(matrix[j][i] for j in range(n))
            if row_set != nums or col_set != nums:
                return False
        return True

ChatGPT 에게 여러번 더 빠르고 성능이 좋은 코드를 요청해보았으나

아쉽게도 더 좋은 코드는 얻지 못하였습니다.

 

그래도 ChatGPT 의 코드는 matrix 에 들어있는 숫자가 꼭 1 ~ n 사이의 숫자가 아니더라도

valid 한 지 체크할 수 있는 코드여서 오.. 좀 더 범용적으로 사용할 수 있겠다라는 생각이 들었습니다.

 

조금 아쉬웠지만 그래도 문제를 그냥 복사 붙여넣기 해도 원하는 의도대로 풀어주는 것은

정말 대단한 것 같았습니다.

읽어주셔서 감사합니다.