[LeetCode] 436. Find Right Interval (Swift, Python)

Find Right Interval - LeetCode

 

풀이

 start 배열에 입력으로 주어지는 intervals 배열의 [i번의 start, i]와 같은 형태로 값을 담아주고 i번의 start를 기준으로 start 배열을 정렬한다. 그 후 intervals를 돌면서 end 값에 대해서 문제에 주어진 조건대로 start를 찾아주는 이분 탐색을 진행했다.

 

코드

[Swift]

typealias startElement = (start: Int, idx: Int)

class Solution {
    // 입력으로 주어지는 intervals 배열들의 start를 담아주는 배열
    // (i번째의 start, i)와 같은 형태로 값을 담아준다.
    var start: [startElement] = []
    
    // 이분 탐색을 위한 메서드
    func bs(_ num: Int) -> Int {
        // left는 0으로 right는 start 배열의 마지막 인덱스로 설정
        var left: Int = 0
        var right: Int = self.start.count - 1
        var res: Int = -1
        
        while left <= right {
            let mid: Int = (left + right) / 2
            
            // start의 값은 unique하므로 end와 일치하는 값을 만나면 바로 해당 idx를 리턴
            // start가 더 클 경우 right를 mid-1로 설정하여 더 작은 값을 찾는다.
            // start가 더 작을 경우에는 left를 mid+1로 설정하여 조건에 맞는 값이 있는지 탐색한다.
            if self.start[mid].start == num {
                return self.start[mid].idx
            } else if self.start[mid].start > num {
                right = mid - 1
                res = self.start[mid].idx
            } else {
                left = mid + 1
            }
        }
        
        return res
    }
    
    func findRightInterval(_ intervals: [[Int]]) -> [Int] {
        // intervals에 1개의 원소밖에 없으면 [-1] 리턴
        if intervals.count == 1 {
            return [-1]
        }
        
        var res: [Int] = [] // 결과를 담아두는 배열
        
        // 먼저 start 배열에 값을 담아주고 정렬을 해준다(이분 탐색을 하기 위해서).
        for i in 0..<intervals.count {
            self.start.append((intervals[i][0], i))
        }
        self.start.sort { $0 < $1 }
        
        // 그리고 intervals의 end 값들에 대해서 이분 탐색을 진행한다.
        for interval in intervals {
            res.append(self.bs(interval[1]))
        }
        
        return res
    }
}

 

[Python]

class Solution(object):

    # 입력으로 주어지는 intervals 배열들의 start를 담아주는 배열
    # (i번째의 start, i)와 같은 형태로 값을 담아준다.
    def __init__(self):
        self.start = []

    # 이분 탐색을 위한 메서드
    def bs(self, num):
        # left는 0으로 right는 start 배열의 마지막 인덱스로 설정
        left = 0
        right = len(self.start) - 1
        res = -1

        while left <= right:
            mid = (left + right) // 2

            # start의 값은 unique하므로 end와 일치하는 값을 만나면 바로 해당 idx를 리턴
            # start가 더 클 경우 right를 mid-1로 설정하여 더 작은 값을 찾는다.
            # start가 더 작을 경우에는 left를 mid+1로 설정하여 조건에 맞는 값이 있는지 탐색한다.
            if self.start[mid][0] == num:
                return self.start[mid][1]
            elif self.start[mid][0] >= num:
                right = mid - 1
                res = self.start[mid][1]
            else:
                left = mid + 1

        return res

    def findRightInterval(self, intervals):
        # intervals에 1개의 원소밖에 없으면 [-1] 리턴
        if len(intervals) == 1:
            return [-1]

        res = [] # 결과를 담아두는 배열

        # 먼저 start 배열에 값을 담아주고 정렬을 해준다(이분 탐색을 하기 위해서).
        for i in range(len(intervals)):
            self.start.append((intervals[i][0], i))
        self.start.sort()

        # 그리고 intervals의 end 값들에 대해서 이분 탐색을 진행한다.
        for (_, end) in intervals:
            res.append(self.bs(end))

        return res