task-scheduler-ii

문제 파악 및 재정의

작업 스케쥴러 ||

순서대로 완료해야 하는 작업을 나타내는 양의 정수 작업의 인덱스가 0인 배열이 제공됩니다. 
여기서 tasks[i]는 i번째 작업의 유형을 나타냅니다.

또한 동일한 유형의 다른 작업을 수행하기 전에 
작업 완료 후 경과해야 하는 최소 일 수를 나타내는 양의 정수 space가 제공됩니다.

모든 작업이 완료될 때까지 매일 다음 중 하나를 수행해야 합니다.

작업에서 다음 작업을 완료하거나 브레이크를 걸어야 합니다.
모든 작업을 완료하는 데 필요한 최소 일수를 반환합니다.

when space 3
  X X 1
1 2 
1 2 [2]
1 2 3 4 5 6 -> 6
space 3
1,2,1,2,1,2,1,2
1 2(_) _ _ 1
1 2 1 2 3 1
array indexing and need duplicated element distance

 

자료구조 및 알고리즘 설계

1 <= tasks.length <= 10^5 (10만)
1 <= tasks[i] <= 10^9 (10억 [기가])
1 <= space <= tasks.length

hashTable
1 [0,2,5]
2 [1,3]
3 [4]

0(1)/2(1)/5(1)
1(1)/3(1)
4(1)
days each task + break days
->
if(duplicated task) + break time
space는 3이지만 가능한 일자는 배열의 idx는 +1 + space
1 2 v v 1 2 3 v 1
1 2 3 4 5 6 7 8 9
  _____
    _____
          _____


space 1
1 1 1 1 1
1 v 1 v 1 v 1 v 1

 

1,2,1,2,3,1
->
key[1, value([0,2,5])]3-(2-0) > -1
key[2, value([1,3])]
key[3, value([4])]

구현

class Solution {
    public long taskSchedulerII(int[] tasks, int space) {
        long days = 0;
        space++;
        HashMap<Integer, Long> lastOccurence = new HashMap<>();
        for (int i = 0; i < tasks.length; i++) {
            if (lastOccurence.containsKey(tasks[i])) {
                long lastTimeOccurred = lastOccurence.get(tasks[i]);
                long daysDifference = days - lastTimeOccurred;
                if (daysDifference < space) {
                    days += (space - daysDifference);
                }
            }
            lastOccurence.put(tasks[i], days);
            days++;
        }
        return days;
    }
    
}

 

회고

https://leetcode-in-java.github.io/src/main/java/g2301_2400/s2365_task_scheduler_ii/

LeetCode-in-Java.github.io

위 문제풀이를 가져다 사용했다

해시테이블이라는 키워드를 보고 요소값을 key로 하고 value를 리스트로 넣어서 표현까지하고 리스트 값 들의 거리가 space보다 작으면 days에 추가해야겠다는 생각까진 했는데 이를 해쉬 맵 contains.key -> if(diff < space)로 쓰는 방법이 떠오르지 않아

결국 답안을 봐버렸다. 너무 아쉬우니 머리가 비워지면 다시 풀어봐야겠다. [ space + 1 ] 해야겠다는 생각도 못했음