Open seungriyou opened 5 months ago
https://leetcode.com/problems/task-scheduler-ii/ similar to #70
hash table dct를 이용하여 {task: recent day}를 기록한다.
dct
{task: recent day}
tasks = [5, 8, 8, 5], space = 2인 케이스를 가정해보면, 다음과 같이 task가 수행되어야 하며, 답은 6이어야 한다.
tasks = [5, 8, 8, 5]
space = 2
6
| day | 1 | 2 | 3 | 4 | 5 | 6 | ---------+---+---+---+---+---+---- | task | 5 | 8 | . | . | 8 | 5 |
tasks를 순회하면서, day를 1씩 증가시킨다.
tasks
day
만약 현재 task가 이전에 등장했다면, space 만큼 지날 때까지 day를 증가시켜야 한다.
task
space
이때, loop를 돌면서 day += 1 하면 TLE가 발생하므로, space를 이용하여 한 번에 day 값을 업데이트 한다. if task in dct and day < (new_day := dct[task] + space + 1): day = new_day
이때, loop를 돌면서 day += 1 하면 TLE가 발생하므로, space를 이용하여 한 번에 day 값을 업데이트 한다.
day += 1
if task in dct and day < (new_day := dct[task] + space + 1): day = new_day
새롭게 업데이트 된 day 값을 dct[task]에 기록한다.
dct[task]
O(n)
n
len(tasks)
O(k)
k
len(set(tasks))
Approach
hash table
dct를 이용하여{task: recent day}를 기록한다.tasks = [5, 8, 8, 5],space = 2인 케이스를 가정해보면, 다음과 같이 task가 수행되어야 하며, 답은6이어야 한다.tasks를 순회하면서,day를 1씩 증가시킨다.만약 현재
task가 이전에 등장했다면,space만큼 지날 때까지day를 증가시켜야 한다.새롭게 업데이트 된
day값을dct[task]에 기록한다.Complexity
O(n)(n=len(tasks))O(k)(k=len(set(tasks)))