[코테 연습] Find Right Interval Python

문제

https://leetcode.com/explore/challenge/card/august-leetcoding-challenge/552/week-4-august-22nd-august-28th/3438/

 

 

문제 이해하는데 걸린 시간 : 7분
첫번째 시도: 32분
결과 : 시간 초과

첫번째 시도 코드 : 시간 초과

배열을 분리해서 key Table 사용하듯이 start point와 end point를 따로 관리하였음

class Solution:
    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
        num = []
        res = []
        length = len(intervals)
        for idx in range(length): #배열 분리
            num.append(intervals[idx][0])
            res.append(intervals[idx][1])

        for idx in range(length):
            minNumArr = [minNum for minNum in num if minNum >= res[idx]]

            if len(minNumArr) < 1:
                res[idx] = -1
            else:
                res[idx] = num.index(min(minNumArr))

        return res

 

 

유력한 후보는 for문안에 for문을 길게 돈다지.. 

혹시나해서 sort가 시간복잡도가 logN으로 더 적어서 아래와 같이 변경하였으나 여전히 시간초과..끙 생각을 아예 다르게 해야겠다. 

   for idx in range(length):
            minNumArr = sorted([minNum for minNum in num if minNum >= res[idx]])

            if len(minNumArr) < 1:
                res[idx] = -1
            else:
                res[idx] = num.index(minNumArr[0])

 

 

두번째 시도: 55분
결과 : 또 시간초과

14 / 17 test cases passed.
Status: Time Limit Exceeded

class Solution:
    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
        startPoints = []
        endPoints = []
        for idx, num in enumerate(intervals):
            startPoints.append((num[0], idx))
            endPoints.append(num[1])

        startPoints=sorted(startPoints)

        for idx,endPoint in enumerate(endPoints):
            for startPoint in startPoints:
                if endPoint <= startPoint[0]:
                    endPoints[idx] = startPoint[1]
                    break
                endPoints[idx] = -1

        return endPoints

 

idx를 가지고다니게 해서 체크하려고 시도함..  for문을 너무 길게 도나?

시간초과나는 배열의 크기를 보면 10000이다. (이 사이트의 장점은 이렇게 wrong case를 알려준다는것 감사합니다..)

배열을.. 시간초과 안나게 하는 방법은.. 이전에 살펴본 문제에서 봤듯이 

1. for문을 가급적 다 돌지않게 break를 적절히 쓰는 것

2. 음.. 반갈..죽..?

아닌데요 그냥 반으로 죽일건데요

 

 

그러면 Array를 반으로 나누어서 동시 탐색을 꾀해보자 그러면 for문 한번 돌 때 두번 탐색하니까 

 

 

 

.....

 

 

두번째 시도: 1시간 40분
결과 : 틀림
이분 탐색조차 금방 구현못하는 재정신 아닌 위지원

startPoints.append(num[0])

내가 뭔가 코드를 잘못 짠듯함... 컴퓨타는 거짓말을 하지 않지

 

 

 

ㅠㅠ.. 드디어 풀었다.

위에서 틀린 이유가 멍청하게 sort해놓고 sort index를 return하고 있었다..ㅠ

2시간,, 우리 할머니도 그것보단 빨리 풀겠다.!

푸는데 걸린 시간 : 2시간

class Solution:
    def findNum(self, startPoints, endPoint):
        leftIdx = 0
        rightIdx = len(startPoints) - 1 # IndexError방지 -1
        resIdx = -1

        while leftIdx <= rightIdx:
            midIdx = (leftIdx + rightIdx) // 2
            if startPoints[midIdx][0] >= endPoint:
                rightIdx = midIdx - 1
                resIdx = startPoints[midIdx][1]
            else:
                leftIdx = midIdx + 1
        return resIdx

    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
        startPoints = []
        endPoints = []
        for idx, num in enumerate(intervals):
            startPoints.append((num[0],idx))
            endPoints.append(num[1])

        startPoints = sorted(startPoints)  # 순서대로 입력이 들어온다는 말을 가정하지 않았음

        for idx, endPoint in enumerate(endPoints):
            endPoints[idx] = self.findNum(startPoints, endPoint)

        return endPoints