[알고리즘] Leetcode #56 구간 병합 (Python)

---

↓↓↓ 아래는 내 리트코드 & 깃허브 계정 ↓↓↓

leetcode.com/Jiwon_Lee/

Jiwon Lee - LeetCode Profile

https://github.com/GodJiLee

GodJiLee - Overview

Leetcode #56 구간병합

• 입력
  [[1,3],[2,6],[8,10],[15,18]]
• 출력
  [[1,6],[8,10],[15,18]]

# 정렬하여 병합
intervals = [[1,3],[2,6],[8,10],[15,18]]

sorted(intervals, key = lambda x: x[0]) # 첫 번째 값 기준으로 정렬

# [[1, 3], [2, 6], [8, 10], [15, 18]]

 

# 전체 코드
def merge(self, intervals):
    merged = []
    for i in sorted(intervals, key = lambda x: x[0]):
        if merged and i[0] <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], i[1])
        else:
            merged += i,
    
    return merged

O(n log n)의 복잡도 소요

sorted() 함수로 intervals를 첫 번째 값 기준으로 정렬시킨 후, 새로 들어온 값의 첫 번째 값이 기존 맨 마지막 리스트의 두 번째 값보다 클 경우에는 단순 merged += i,로 붙이고, 작거나 같은 경우에는 기존 두 번째 값을 merged[-1][1]과 i[1] 중 큰 값으로 변경한다. 

 

콤마(,) 연산자

a = [1]

b = [2, 3]

a += b

a # [1, 2, 3]

 

단순히 += 연산을 하면 concat과 같은 결과

a = [1]

b = [2, 3]

a += b,

a # [1, [2, 3]]

 

중첩 리스트로 반환됨

a += [b]

a # [1, [2, 3]]

 

대괄호 사용하는 것과 동일한 결과