(간단한 코드)리트코드 56. Merge Intervals

 

블로그를 찾아본다는 것은 이미 이 문제의 뜻을 알고 있다고 생각한다.

 

우리는 이 문제에서 주의해야 할 점이, "문제에서 리스트 안의 원소가 순서대로 나열되어 있다는 말이 없다"는 것이다.

 

다른 말로는 순서가 뒤죽박죽일 수 있으니, 우선 "정렬"을 해주는게 최우선이다.

1.sort와 lambda를 활용한 리스트 순서 정렬하기

intervals.sort(key = lambda interval : interval[0])

 

이게 가장 먼저 해야 하는 코드다. 

 

해석은 다음과 같다: 우선 sort(key = )라고 하면, "무엇을 기준으로 순서를 나열 할 것"인지 정하는 부분이다.

 

lambda interval : interval[0]에서 lambda는 함수를 짧게 만든 것이라는 것을 어디선가 들었을 것이라고 생각한다. 

(실제로는 그렇게 자주 쓰이지 않는다) 

 

여기서 "interval"는 아직 정해지지 않은 변수 명인데, 어떻게 바로 쓸 수 있는가?라는 의문이 들었지만, 이는 다음과 같이 생각해야 한다.

lambda interval : interval[0]
->
def indexing(interval): #받는 인자값의 이름이 interval라고 설정한 것이다.
	return interval[0]

 

일반적인 함수는 "함수 이름"(여기서는 indexing)이 필요한데, lambda는 이를 스킵하는 것이다.

 

대신 "lambda 매개변수 : 표현식" 에서 표현식은 "매개변수"로 이루어져야 한다.

 

여기서 또 하나 알아야 하는 것은 sort(key = )라고 하면, "정렬할 리스트의 원소를 매개변수로 받는다"라는 것이다. 

 

따라서 아래 코드에서는 intervals에 있는 원소들이 하나하나씩 interval에 들어가는 것이다. 

intervals.sort(key = lambda interval : interval[0])
#만약에 intervals = [[1,2],[2,3]] 이면
#첫 번째 시도에서는 interval = [1,2]의 0번째 원소 -> 1
#두 번째 시도에서는 interval = [2,3]의 0번째 원소 -> 2
#이런 식으로 나온 값들을 기준으로 정렬을 한다는 것이다.

 

2.문제풀이

우선 전체 코드는 아래와 같다.

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key = lambda interval : interval[0])
        merged = []

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

 

여기서는 우선 비교해야 할 대상을 정의하자:

(1) merged 리스트 안에 있는 "마지막 요소(리스트)" -> 코드에서는 merged[-1]로 나타낸다.

(2) 새롭게 비교해야할 요소(리스트) -> 코드에서는 interval로 나타낸다.

 

비교 대상 2가지는 다음과 같이 3가지 상황을 비교한다(맨 첫번째는 merged안에 아무것도 없을 경우를 의미한다)

 

첫번째와 세번째 상황(그냥 추가만 하면되는 상황)을 첫번째 if문으로 해결

두번째 상황을 else 부분에, merged의 맨 마지막 부분을 갱신하는 것으로 해결 -> merged[-1] 갱신(update라고 말을 많이한다)