1월 3주차 코딩 테스트

1. 활동 선택

풀이

이 문제는 그리디 문제로 회의실 배정 알고리즘에 속한다.

풀이 방법은 모든 조합을 따져보는 방법이나 이는 너무 시간이 오래걸린다.

따라서 많은 회의를 진행하기 위해서는 최대한 빨리 회의가 끝나야 한다는 관점으로 풀이해야 한다.

제일 빨리 끝나는 회의를 기준으로 겹치는 회의는 제거한다.

그러면서 다음 겹치지지 않는 가장 빨리 끝나는 회의를 찾는 것이다.

이렇게 계속 빨리 끝나는 회의를 선택하는 것이 가장 많은 회의를 할 수 있는 방법이다.

이미 선택한 활동 시간에 대해서는 activity에서 제거하도록 하여 activity가 빈 리스트가 때까지 반복하도록 하였다.

그리고 여기서 핵심 포인트는 제거할요소의 인덱스를 remove 배열에 담고, 이후 탐색이 끝난 후 순차적으로 제거하는데, 제거할 인덱스를 뒤쪽부터 적용해줌으로써 인덱스 밀림 현상을 해결한다는 것이다.

예를들어 배열 [1, 2, 3, 4]가 있을 고 remove배열이 [2, 3] 이라 하자.

pop(2)를 하면 3이 제거되게 되고 [1, 2, 4] 가 남게된다. 이후 여기서 pop(3)을하면 index out of range 에러가 나타난다.

그러나 거꾸로 3을제거하고 2를 제거하면 [1, 2, 3, 4] → [1, 2, 3] → [1, 2] 가 되어 순조롭게 제거가된다.

그러나 무엇때문인지 테스크 케이스에서 실패한다.

def solution(activity):
    activity.sort(key = lambda x: (x[1], x[0]))
    i = ans = 0
    while activity:
        start, end_time = activity.pop(0)
        remove = []
        i = 0
        while i < len(activity):
            if end_time <= activity[i][0]:
                end_time = activity[i][1]
                remove.append(i)
            i += 1
        
        for j in sorted(remove, reverse=True):
            activity.pop(j)
        
        ans += 1
        
    return ans

이 문제를 해결하고자 라인 스위핑 알고리즘으로 풀이해본다.

라인 스위핑(Line Sweeping) 알고리즘

각 활동 (s, e)을 시작 이벤트, 끝 이벤트로 분리한다.

(s, +1): s시점에 새로운 활동이 1개 추가됨
(s, -1): s시점에 새로운 활동 1개가 종료됨

“동시에 열려 있는 활동 수”를 구할 수 있다.

for s, e in activity:
    events.append((s, +1))  # 시작 이벤트
    events.append((e, -1))  # 끝 이벤트

시간이 같다면 -1(끝)이 +1(시작)보다 먼저 오도록 한다.

왜냐하면 [(4, 5), (5, 9)]가 있다면 events = [(4, 1), (5, -1), (5, 1), (9, -1)]로 구성되어 이 둘은 겹치지 않는다.

events.sort(key=lambda x: (x[0], x[1]))

정렬된 이벤트를 시간순으로 하나씩 확인하면서 delta값 +1, -1을 누적하여 최대 동시 활동수를 구한다.

그 이유는 동시에 몇 개의 작업이 겹치는지의 최대값을 구하면 그것이 모든 작업을 처리하기 위해 최대 몇명이 필요한지와 동일하기 때문이다.

current = 0
max_concurrent = 0
for _, delta in events:
    current += delta
    max_concurrent = max(max_concurrent, current)

예를들어 아래와 같이 구성되어 있다고 하자.

activity = [[0, 5], [2, 6], [3, 5], [7, 10], [5, 9], [13, 15]]

이를 시각화해보자.

그리고 activity를 정렬까지 완료한다면 아래처럼 구성된다.

(0, +1),
(2, +1),
(3, +1),
(5, -1), (5, -1), (5, +1),
(6, -1),
(7, +1),
(9, -1),
(10, -1),
(13, +1),
(15, -1)

구성이 완료되면 시간 우선순위로 시작이 되면서 +1이되면 새로운 이벤트의 시작, -1을 만나면 진행중이였던 이벤트가 종료되는 것이다.

따라서 delta값을 누적함으로써 최대 동시 진행중인 갯수를 구한다.

전체코드는 아래와 같다.

def solution(activity):
    events = []
    for start_time, end_time in activity:
        # 시작 이벤트: (시간, +1)
        # 종료 이벤트: (시간, -1)
        events.append((start_time, +1))
        events.append((end_time, -1))

    # (시간, delta) 오름차순 정렬
    # 시간 같으면 -1(끝)이 +1(시작)보다 먼저 처리됨
    events.sort(key=lambda x: (x[0], x[1]))

    current = 0
    max_concurrent = 0

    for _, delta in events:
        current += delta  # 시작이면 +1, 끝이면 -1
        max_concurrent = max(max_concurrent, current)

    return max_concurrent

이번엔 테스트 케이스는 전부 통과하지만 효율성 테스트에서 실패한다.

우선순위 큐

이번엔 우선 순위 큐로 풀이해보자

시작 시간을 기준으로 활동을 정렬한 후, 종료 시간을 우선순위 큐(최소 힙)에 저장한다.

각 활동의 시작 시간이 큐에 있는 종료 시간의 최솟값보다 크거나 같다면, 해당 종료 시간을 큐에서 제거한다.

이 과정을 반복하며 큐의 크기를 갱신하고, 최댓값을 기록하여 동시에 처리 가능한 활동의 최대 개수를 구하는 방식이다.

import heapq

def solution(activity):
    activity.sort(key=lambda x: x[0])
    
    heap = []  
    max_rooms = 0
    
    for start, end in activity:
        if heap and heap[0] <= start:
            heapq.heappop(heap)
        
        heapq.heappush(heap, end)
        max_rooms = max(max_rooms, len(heap))
    
    return max_rooms

https://wikidocs.net/206266

TestCase

# 테스트 1
입력값 〉 [[0, 5], [2, 6], [3, 5], [7, 10], [5, 9], [13, 15]]
기댓값 〉 3

출처

해당 문제와 코드는 제로베이스(ZeroBase)에서 제공받았습니다.

1월 3주차 코딩 테스트

목차

1. 활동 선택

풀이

라인 스위핑(Line Sweeping) 알고리즘

우선순위 큐

TestCase

출처

Comment