[LeetCode] 1943. Describe the Painting

I. Description

문제 링크: https://leetcode.com/problems/describe-the-painting/description/?envType=problem-list-v2&envId=hash-table

---

II. Code

i)

class Solution:
    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:
        # events 초기화
        events = defaultdict(int)
        
        # 사건들 기록
        for start, end, color in segments:
            events[start] += color
            events[end] -= color
            
        result = []
        prev, color = None, 0
        for current in sorted(events):
            if color: # if color == 0, 그 부분이 합 0임을 의미
                result.append([prev, current, color])
            
            color += events[current]
            prev = current
            
        return result

사건을 기록하고 시간순으로 정렬한 뒤 차례로 진행했던 1942번 문제와 유사한 방식으로 풀 수 있었다. sorted가 가장 시간복잡도를 많이 차지하므로 전체 시간복잡도가 O(nlogn)이다.

추가로 dictionary를 정의할 때 defaultdict(int)로 정의하는 방법도 있다. 이렇게 하면 dict에 아직 key 값 1이 존재하지 않아도 events[1] += 5를 진행할 수 있다. 존재하지 않는 key 값이라도 기본값을 0으로 둬 5를 더할 수 있는 원리다.

 

여러 실패한 케이스도 있었다.

ii)

# Example 3의 경우, 합은 같은데 color sets가 달라서 구분해야 하는 경우를 하기 어려움.
class Solution:
    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:
        # 변수값 초기화
        painting_list = [0] * 100001
        max_time = 0
        
        # painting_list = [0, 14, 14, 14, 16, 16, 16, 0, 0, ...]
        for segment in segments:
            start, end, value = segment
            for i in range(start, end):
                painting_list[i] += value
            max_time = max(max_time, end)
                
        result = []
        start = None
        for i in range(max_time + 1):
            # 처음 14를 만나면 start = 1
            if painting_list[i] > 0:
                if start is None:
                    start = i
                elif start is not None and painting_list[i] != painting_list[i - 1]:
                    result.append([start, i, painting_list[start]])
                    start = i  
            else:
                if start is not None:
                    result.append([start, i, painting_list[start]])
                    start = None
            
        return result

최대 시간이 10*5이므로 각 시간에 대한 color의 합을 기록하면 되겠다고 생각했다. 하지만 Example 3와 같은 경우, 합은 같은데 color sets가 달라 구분해서 결과를 출력해야 하는 경우를 해결하기 어려웠다.

 

iii)

# Memory Limit Exceeded Error
class Solution:
    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:
        # 변수값 초기화
        painting_list = [set() for _ in range(100001)]
        max_time = 0
        
        # painting_list = [0, 14, 14, 14, 16, 16, 16, 0, 0, ...]
        for segment in segments:
            start, end, value = segment
            for i in range(start, end):
                painting_list[i].add(value)
            max_time = max(max_time, end)
            
        result = []
        start = None
        prev = None
        for i in range(max_time + 1):
            current = painting_list[i]
                
            if current:
                if start is None:
                    start = i
                elif start is not None and current != prev:
                    result.append([start, i, sum(prev)])
                    start = i
                prev = current
            else:
                if start is not None:
                    result.append([start, i, sum(prev)])
                    start = None
            
        return result

비슷한 방식인데 합 대신 color sets를 기록하면 어떨까 해서 해봤으나 Memory Limit Exceeded 에러에 걸렸다. 따라서 Hash Table 방식으로 풀고자 고민했고 1번 풀이를 생각할 수 있었다.