Algorithm/문제풀이

[LeetCode] LeetCoe 1337. The K Weakest Rows in a Matrix - python3

Razelo 2022. 6. 26. 16:51

재밌는 문제를 찾았다. 

 

그리고 최근에 느낀거지만 Leetcode 에서 submit 을 하면 성능과 메모리가 어느정도 되는지 나오는데 그걸 줄여보려고 코드를 바꾸려고 했던 적이 많다. 근데 확실해진건 이걸 기준으로 성능, 메모리 최적화를 하긴 어렵다는 것이다.

 

그 이유는 그 결과가 항상 다르기 때문이다. 즉 그냥 근사치 정도가 아니다. 90퍼센트 효율이 뜨던 코드가 갑자기 10퍼센트 효율이 뜨는 경우도 있다. 

 

그래서 그냥 이런 성능이랑 메모리 효율성을 따지기 보다 그냥 코드만 보기좋게 다듬는 연습을 하는게 더 낫다는 생각이 들었다. 

 

그런데 마침 오늘 꽤 괜찮은 문제를 발견했고 최대한 코드를 줄여보려고 노력을 했는데 list comprehension의 한계에서 막혔다. 

 

즉 list comprehension 를 적극 활용해서 코드를 줄일 수 있었지만 코드 내에서 assign을 하기에는 부족함이 있었다. 관련해서 찾아보았지만 나와는 맞지 않는 해결법들이 나왔다. 참고로 파이썬의 새로운 기능에는 := 라는 키워드가 추가되었다고 한다. (바다코끼리 연산자)

 

나도 처음 보는 키워드라서 뭔가 싶었지만 얼추 사용예를 살펴보니 내가 원하는 방식으로 동작할 수 없는 키워드였다. 참고로 내가 원하는건 list comprehension 내에서 list 본인에 요소를 할당함은 물론이고 다른 list 의 값을 수정하는 행위까지 하려고 했다.  (그런데 왜 될것만 같지... 방법이 있을것같은 느낌이 든다.)

 

일단 코드를 줄여나가기까지의 과정은 아래와 같다. 

 

첫번째 접근은 아래와 같다. (정답 솔루션)

'''
~ 400

Runtime: 137 ms, faster than 68.20% of Python3 online submissions for The K Weakest Rows in a Matrix.
Memory Usage: 14.5 MB, less than 13.92% of Python3 online submissions for The K Weakest Rows in a Matrix.

코멘트: 
꽤나 재밌는 문제다. 그런데 로직 중 한군데를 살짝 이상하게 짜서 10분 정도를 낭비했다. 
지금 아래 코드가 꽤나 긴데 문제 자체가 쉬운것에 비하면 지나치게 길다. 이거 충분히
짧게 만들 수 있을 것 같다. -> 개선해봅시당. 
'''

class Solution:
    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
        li = [0] * len(mat)
        for i in range(len(mat)):
            li[i] = mat[i].count(1)
        
        print(f'li:{li}')
        sorted_li = sorted(li)
        print(f'sorted_li:{sorted_li}')
        result = [0] * k
        j = 0
        for i in range(len(sorted_li)):
            print(f'li in loop :{li}')
            result[j] = li.index(sorted_li[i])
            idx = li.index(sorted_li[i])
            li[idx] = -1
            j += 1
            if j == k:
                break
        print(li)
        print(result)
        return result

 

두번째 접근은 아래와 같다.  (정답 솔루션)

'''
Runtime: 214 ms, faster than 16.04% of Python3 online submissions for The K Weakest Rows in a Matrix.
Memory Usage: 14.2 MB, less than 87.40% of Python3 online submissions for The K Weakest Rows in a Matrix.

개선한 솔루션: 
역시 list comprehension 이 상당히 좋다. 그냥 가독성이 너무 좋다. 
근데 여기서도 더 줄일 수 있을까? 그리고 항상 leetcode 풀면서 느끼는 거지만 실행속도와 메모리가
매번 돌릴때마다 다르게 나온다. 근사치가 아니라 완전 상이한 값이 나온다. 즉 릿코에서 
이걸로 잘짰는지 못짰는지 평가할게 못된다. 그냥 코드나 이쁘게 짜는게 나을듯. 
'''

class Solution:
    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
        li = [row.count(1) for row in mat] # list comprehension 으로 수정해서 코드 줄였음. 
        sorted_li = sorted(li) 
        
        result = [0] * k
        j = 0
        for i in range(len(sorted_li)):
            idx = li.index(sorted_li[i])
            result[j] = idx
            li[idx] = -1
            j += 1
            if j == k:
                break
                
        return result

 

세번째 접근은 아래와 같다. 참고로 이 세번째 접근에서 문제가 생겨서 세번째 접근은 불가능하다는 것을 알게 되었다. 

list comprehension을 최대한 활용하려 했지만 그러지 못했다. (오답 솔루션)

'''
개선했지만 오답인 솔루션: 
여기까지는 어떻게 list comprehension 으로 바꿔줬는데 list comprehension에서 선언문을 
실행안될것같은데...즉 위 코드에서 보면 -1 로 설정하는 부분이 있는데 즉 할당이 list comprehension
에서 이뤄질 수 있는지 모르겠다. 이건 찾아보자. 

:= 엱산자를 통해서 할당할 수 있는 기능이 있다는 답변이 Stackoverflow 에 있었는데 나와 같은
경우에 사용할 수 있는 연산자가 아니다. 즉 list comprehension 내에서 한번에 끝낼 수 있는 
방법이 아니다. 

근데 왜 이거 bit operation 사용하면 될 것 같지... 
bit or 혹은 xor 어떻게 써보면 될 것 같은데, 
'''
class Solution:
    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
        li = [row.count(1) for row in mat] 
        sorted_li = sorted(li) 
        result = [li.index(val) for val, count in zip(sorted_li, list(range(k))) if count <k]
        return result

 

위 솔루션에서의 접근법은 불가능하다는 것을 확인했다. 

 

그리고 이후에 한참을 시도해봤는데 결정적인 답을 얻었다. 아예 list comprehension 내에서 할당문이 불가능한 것을 확인했다. 

 

생각해보니 꼭 list comprehension 이 아니라 특정 구문에서 assign을 시도하는 것 자체가 불가능한 경우를 이전에도 수도없이 보았지만 list comprehension이 만능이라는 착각을 했던 것 같다. 

 

아래 첨부 사진을 보자. 

 

6번 라인에서 Runtime Error 가 발생했다. 

이유인 즉슨 invalid syntax 이다. 아예 문법이 틀리다는거다. 그런데 어디가 틀리다고 지적하고 있을까? 

파란색 동그라미 친 곳을 보자. assign 기호가 문제라고 명확하게 알려주고 있다. 

 

즉 어떤 형태로든 이 안에서 assign 은 불가능하다.

 

요즘 여유가 생겨서 이렇게 솔루션 하나를 뜯어볼 시간이 있는데 그게 너무 좋다. 

 

학기다니는 동안 너무 바빠서 이렇게 코드 하나 길게 쳐다보는게 아깝다는 생각이 들었었다. 물론 좋지 못한 생각이다. 이런 고민은 꼭 필요하니까. 어쨋든 재밌는 문제다. 

 

참고로 위에서 언급한 := 키워드는 아래 stackoverflow 에서 참고할 수 있다. 내가 how can i do assigments in a list comprehension 이라고 검색했는데 나랑 똑같은 고민을 하는 사람이 있었나보다. 읽어보면 좋겠지만 list comprehension 내에서 assign 까지 한번에 해버리는 답은 아니다. 

 

assign 동작 하나만 할 사람이라면 := 를 쓰는게 맞다. 나는 assign + list요소 추가 까지 한번에 하려고 하는게 문제였다. 

 

참고로 이 키워드는  the walrus operator. 라고 불린다. 

 

https://stackoverflow.com/questions/10291997/how-can-i-do-assignments-in-a-list-comprehension

 

How can I do assignments in a list comprehension?

I want to use the assignment operator in a list comprehension. How can I do that? The following code is invalid syntax. I mean to set lst[0] to an empty string '' if it matches pattern: [ lst[0] ...

stackoverflow.com

 

아래와 같이 사용하면 된다. 

특정 상황에서는 꽤나 유용하게 쓰일 수 있을 것 같다. 하지만 어떻게 보면 굳이 이걸 써야할 상황이 자주 올것같진 않다. 꼭 필요한 상황이 있을 건데 대부분의 상황에서는 오히려 무조건 변수에 할당을 해서 풀어내야하는 순간이 온다면 내 접근법이 틀리진 않았는지 다른 방법이 있는지를 한번 더 생각해보는게 좋을 것같다. 


참고로 글 쓰고 난 이후에 좀더 만지작 거렸는데 해봐도 마땅한 수가 나오지 않는다. 혹시 방법이 있을지도 모른다. 내가 모르는 무언가 방법이 있을거라는 생각이 든다. bit operation을 사용하면 가능할것 같은 느낌이 드는데 감이 안잡힌다. 

 

그리고 아래 런타임 에러를 보면 확실하게 알 수 있다. 

cannot use assignment expressions with subscript 

 

 

반응형