99클럽 TIL (240820)

> [Middler] Find Right Interval

https://leetcode.com/problems/find-right-interval/

 

 

문제 풀이 과정

문제 풀이 방법을 떠올리기 쉽지 않았다. 이전 문제와 동일하게 이분탐색으로 풀면되겠지만, 아직 풀이 방법이 익숙하지 않은 것 같다. 그래서 풀이방법을 참조했다.

 

우선 해당 interval 요소별로 right interval의 인덱스를 담은 리스트를 리턴한다. 만일 없는 경우 -1을 담아 리턴한다. right interval의 조건은 i번째 interval의 end와 j번째 interval의 start를 비교해서 j번째 interval의 start >= i번째 interval의 end 일 때, 해당 j는 i 의 right interval이라고 할 수 있다.

 

[풀이 과정]

1. intervals 배열을 (index, 해당 index의 interval요소 중 start) 튜플 형태로 묶어 start 오름차순 기준으로 정렬한다. (sorted_start)

2. intervals 를 for loop 돌며 각 원소의 end요소가 sorted_start 배열 원소들보다 같거나 큰 인덱스를 리턴한다.

3. 리턴된 인덱스가 intervals의 길이와 같다면 start < end 이므로 -1을 담는다.

4. 리턴된 인덱스가 intervals의 길이와 같지 않다면 res[i] = sorted_start[j][0] 을 담는다.

 

문제 풀이

python

class Solution:
    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
        # start(i) 를 오름차순으로 정렬 : (i,start(i))
        # ex2 [(0,3),(1,2),(2,1)] -> [(2,1),(1,2),(0,3)]
        sorted_start = sorted(enumerate( k for k,v in intervals), key=lambda x:x[1])
        res = [-1] * len(intervals)

        def bs(start, end, target) :
            while start <= end :
                mid = (start+end)//2
                if sorted_start[mid][1] == target :
                    return mid
                elif sorted_start[mid][1] < target :
                    start = mid + 1
                else :
                    end = mid - 1
            return start

        for i, interval in enumerate(intervals) :
            # sorted_start에서 end(i)가 start(i)보다 작은 위치를 리턴
            j = bs(0, len(intervals)-1, interval[1]) 
            if j != len(intervals) :
                res[i] = sorted_start[j][0]

        return res

 

시간복잡도 O(NlogN)

 

회고 및 느낀점

이분탐색 문제 풀이를 많이 해봐야 겠다. 영 어렵네

 

---

> [Beginner] Arranging Coins

https://leetcode.com/problems/arranging-coins/submissions/1362083237/

 

 

문제 풀이 과정

[첫번째 풀이] 성공

단순 반복문으로 풀었다. 우선 n을 i+1(=행의 순서)만큼 빼주면서 n - (i+1) 이 0보다 작아질때 i+1을 리턴하면된다. 다풀어놓고 보니 지저분하기도하고 binary search로 분류되어 있어서 다시 그렇게 한번 풀어보았다.

class Solution:
    def arrangeCoins(self, n: int) -> int:
        
        for i in range(n) :
            n -= i+1
            if n - (i+1) <= 0 :
                return i+1

        return 0

 

 

문제 풀이

python [두번째 문제 풀이] 

여기서 내가 몰랐던 수학 개념 '등차 수열의 합'

첫째 항부터 n항 까지의 등차수열의 합을 구할 때, 아래의 공식을 이용한다. 문제를 풀기 위해 이분탐색과 등차 수열의 합을 이용했다.

동작 과정

1. start, end 를 초기화 한다.

2. start, end의 중간점인 mid를 구한다.

3. 등차 수열의 합 공식을 이용해 1 ~ mid 까지의 sum을 구한다.

4. sum과 입력값 n을 비교한다.

class Solution:
    def arrangeCoins(self, n: int) -> int:
        start, end = 1, n
        while start <= end :
            mid = (start+end) // 2
            temp = int(mid*(mid+1) // 2)
            if temp == n :
                return mid
            if temp < n :
                start = mid + 1
            else :
                end = mid - 1

        return end

 

시간복잡도 O(NlogN)

 

회고 및 느낀점

어려워~광광