Data Structure and Algorithm/코딩테스트준비

LeetCode - 1037. Valid Boomerang 솔루션 - python

Razelo 2022. 6. 18. 21:14

꽤 쉬운문제라고 생각하고 풀었는데 생각치 못한 부분에서 막혀서 답지를 보고 푼 문제이다. 

 

참고로 블로그에 기록해두는 이유는 답지를 보고 풀었는데 거기서 꽤 많은 점을 배울 수 있었기 때문이다. 

 

아래는 문제 링크이다. 꽤 간단한 문제이다. 

https://leetcode.com/problems/valid-boomerang/

 

자 그렇다면 내가 처음 접근한 오답을 먼저 보자. (이 코드 안봐도 된다. 아예 틀리기도 했고 너무 부실하다. )

 

class Solution:
    def isBoomerang(self, points: List[List[int]]) -> bool: 
        points = sorted(points)
        last_point = points[-1][0]
        
        for i in range(1, 3):
            if points[i - 1] == points[i]:
                return False 
        
        count1 = 0
        for i in range(1, 3):
            if points[i - 1][0] == points[i][0]:
                count1 += 1
        if count1 >=2:
            return False 
        
        count2 = 0
        for i in range(1, 3):
            if points[i - 1][1] == points[i][1]:
                count2 += 1
        if count2 >=2:
            return False 
        
        count = 0 
        for i in range(1, last_point + 1):
            if points[0] == [i, i]:
                count += 1
            if points[1] == [i, i]:
                count += 1
            
        if count >= 2:
            return False
        return True

 

이 코드는 그냥 안봐도 된다. 틀리기도 했고 기울기를 비교해주지 않았다. 그리고 너무 길다. 

 

아래는 정답 솔루션이다. 확실히 코드가 깔끔하다. 

 

class Solution:
    def isBoomerang(self, points: List[List[int]]) -> bool: 
        x_points = list(set(list(zip(*points))[0]))
        y_points = list(set(list(zip(*points))[1]))
        
        if len(set(map(tuple, points))) != 3: return False 
        if len(x_points) == 1: return False
        if len(y_points) == 1: return False 
        if len(x_points) ==2 or len(y_points) == 2: return True 
        
        slope1 = (points[1][1] - points[0][1]) / (points[1][0] - points[0][0])  
        slope2 = (points[2][1] - points[1][1]) / (points[2][0] - points[1][0])
        
        return False if slope1 == slope2 else True

지금 보면 zip을 사용할때 *points 를 사용하는 것을 볼 수 있을 것이다. 이렇게 하면 뒤에 [0]을 했을때 각 0번째 요소만 뽑아낼 수 있다. 이걸 배웠고 그리고 또 하나 배운게 더 있다. 첫번째 if 문에서 points 를 set 으로 잡아줄때 map 을 적용해서 tuple 로 만들어내는걸 볼 수 있을 거다.

 

그냥 set으로 바꿔버리면 안될까? 안된다.

 

그렇게 한다면 TypeError: unhashable list 라는 에러를 마주하게 될 거다. 즉 List[List<T>] 인 자료구조에서 내부에 List가 요소로 존재하는 리스트인데 이걸 set 으로 바꿀 순 없다는 거다. 그래서 tuple 로 바꿔준 다음에 set 으로 잡아줘야 한다. 

그렇게 distinct 한 지점들이 있는지 없는지에 대한 판별을 진행한다. 

 

그리고 두세번째 if문에서 len(x_points), len(y_points) 에 대한 if문이 존재하는것도 개수가 1인지를 체크한다. 즉 모든게 같은 지점이라면 1이 나올터이니 당연히 걸러내야 한다. 

 

자 그리고 마지막 부분이 내가 생각지 못했던 부분이다. 

slope1 과 slope2 를 계산하는 부분이 있다. 즉 기울기를 계산하는 부분이다. 

 

이렇게 계산해서 기울기가 같다면? 대각선이라는 거다. 그러니 False 를 리턴하고 대각선이 아니라면 True 를 리턴한다. 

 

이 코드는 상당히 짧다. 그럼에도 불구하고 많은걸 배울 수 있었다. 

반응형