[코테] 리트코드 파이썬 - 54번, 55번, 56번

54번 Spiral Matrix

Spiral Matrix - LeetCode

LeetCode - The World's Leading Online Programming Learning Platform

2차원 리스트를 시계방향으로 spiral 모양으로 읽어드린 결과를 리턴하는 문제이다.

 

우선 방향을 순서대로 동 -> 남 -> 서 -> 북의 시계방향으로 돌아갈 수 있게끔 dx, dy를 설정하였다. 해당 방향으로 리스트를 읽어나가다가 한쪽 끝(범위 밖)에 도달하거나 이미 방문한 곳이라면 다른 방향으로 넘어간다. 방향이 넘어감을 표시하기 위해 cnt라는 변수를 사용하였다.

리스트를 읽어나갈 때는 원소가 가질 수 있는 값을 초과한 값으로 방문 표시를 했다.

반복문의 종료 조건은 읽은 방향의 값이 4가 넘어가 모든 방향을 조사했다면 종료하였다. 이를 위해 first라는 변수를 사용하였다.

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        dx=[0,-1,0,1]
        dy=[1,0,-1,0]
        cnt=0
        first=0
        result=[]

        x,y=0,0
        while True:
            cx,cy=0,0
            if len(result)!=0:
                cx=x+dx[cnt]
                cy=y+dy[cnt]

            if cx>len(matrix)-1 or cy>len(matrix[0])-1 or cx<0 or cy<0:
                if first>4:
                    break
                first+=1
                if cnt<3:
                    cnt+=1
                else:
                    cnt=0
                continue

            if matrix[cx][cy]!=101:
                first=0
                result.append(matrix[cx][cy])
                matrix[cx][cy]=101
                x,y=cx,cy
                continue
            else:
                if first>4:
                    break
                first+=1
                if cnt<3:
                    cnt+=1
                else:
                    cnt=0

        return result

---

55번 Jump Game

Jump Game - LeetCode

LeetCode - The World's Leading Online Programming Learning Platform

인덱스의 값만큼 점프할 수 있다고 가정했을 때, 마지막 인덱스에 도달할 수 있으면 true 아니면 false를 출력하는 문제이다.

 

인덱스의 값을 연료라고 가정했을 때, 원소를 하나씩 지나치면서 연료가 1씩 떨어지도록 세팅한다.

만약, 연료의 값이 0 미만이 된다면 끝 인덱스까지 못 가서 멈춘 것이므로 false를 리턴하고 아니라면 true를 리턴한다.

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        gas = 0
        for n in nums:
            if gas < 0:
                return False
            elif n > gas:
                gas = n
            gas -= 1
            
        return True

---

56번 Merge Intervals

Merge Intervals - LeetCode

LeetCode - The World's Leading Online Programming Learning Platform

리스트의 첫번째 원소가 범위의 시작이고 두번째 원소가 범위의 끝을 나타낼 때, 겹치는 범위가 있다면 이를 통합하여 리턴하는 문제이다.

처음 시도로는, 주어진 리스트i 끝점과 리스트i+1의 시작을 비교하여 겹치는 범위를 확인하였다. 만약 겹치는 범위가 있다면 리스트i의 시작과 (리스트i의 끝점과 리스트i+1의 끝점 중 최댓값)을 통합범위로 하여 결과 리스트에 넣었다.

만약 겹치는 범위가 없다면 주어진 리스트i를 바로 결과 리스트에 넣었다.

def merge2(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        result=[]
        cnt=0

        while True:
            if cnt>len(intervals)-1:
                break
            elif cnt==len(intervals)-1:
                result.append([intervals[cnt][0],intervals[cnt][1]])
                break

            if intervals[cnt][1]>=intervals[cnt+1][0]:
                one=max(intervals[cnt+1][1],intervals[cnt][1])
                result.append([intervals[cnt][0],one])
                cnt+=2
            else:
                result.append([intervals[cnt][0],intervals[cnt][1]])
                cnt+=1

        return result

해당 방법은 바로 앞 뒤의 범위만 확인할 수 있었고 여러 개가 통합되는 범위일 경우를 처리하지 못했다.

 

그렇기 때문에 범위의 시작값을 기준으로 정렬한 뒤, 통합되지 않는 범위는 결과 리스트에 넣고 다시 결과리스트의 마지막 인덱스와 다음 범위를 비교하는 방식으로 구현한다면 모든 테스트를 통과할 수 있다.

이때, 통합되는 범위는 마지막 인덱스의 끝점을 변경해줌으로써 결과리스트를 변경한다.

    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals = sorted(intervals, key=lambda x: x [0])

        ans = []

        for interval in intervals:
            if not ans or ans[-1][1] < interval[0]:
                ans.append(interval)
            else:
                ans[-1][1] = max(ans[-1][1], interval[1])
        
        return ans