https://leetcode.com/problems/task-scheduler/
나의 논리
우선 구현을 못해서 풀지 못한 문제이고 나중에 힌트를 얻어서 풀긴했다. (https://withhamit.tistory.com/419 여기 참조)
논리자체는 내가 생각했던거랑 맞았다.
대부분의 이런 문제의 실제로 문자열 및 리스트를 조작하면서 시뮬레이션을 돌리진 않아도 된다.. 이것만 생각해도 시간복잡도를 줄일 방법을 많이 생각 할 수 있다고 본다.
내가 생각한 방법은 그리디 방법으로 하나의 알파벳을 무조건 N 인터벌만큼 떨어뜨려놓고 시작하는것이다. 가장 많이 등장한 알파벳을 N인터벌 단위로 놓고, 두번째로 많이 등장한 단어를 인터벌 사이에 넣고 N간격만큼 떨어뜨리고..이걸 반복하면 되겠다고 생각했다.
그러나 정확하게 맞은 논리는 아니어서 구현에 어려움을 격었다.
정답 논리
가장 많이 등장하는 단어를 일단 N 인터벌만큼 떨어뜨려 놓고 시작하는것은 맞다. 다른 점은 그 다음 단어를 어떻게 배치할것인가이다.
하지만 더 이상의 인터벌은 고려하지 않아도 된다.왜냐하면 이 문제의 핵심은 가장 자주 등장하는 단어들을 N만큼 떨어뜨려놓고 그 안에 나머지 단어들을 배치하여 최소길이를 반환하는것이기 때문이다.
단어를 배치하는 방법은 단어의 갯수가 인터벌의 개수보다 적다면 하나의 인터벌에 하나의 단어를 배치하면 되고, 그 반대라면 인터벌의 갯수만큼 배치하고 나머지 단어는 맨끝 단위 뒤쪽에 배치하면 된다.
그리고 정답의 길이는 tasks의 길이보다 짧을 수는 없다.
tasks의 길이에 단어를 적절히 배치하고 남은 idle의 수를 더해서 반환하면 된다.
예를 들면
- [A,A,A,B,B] n = 2 인 경우
가장 빈도수가 높은 단어를 먼저 N간격으로 배치한다.
A _ A _ A
그 후 A 사이의 공간을 1 인터벌이라고 하면 A의 갯수 -1개의 인터벌이 생기는데 이 사이에 B를 배치하면 된다.
AB_AB_A 또는 A_BA_BA가 될 수 있다.
- [A,A,A,B,B,B] n =2 인 경우
AAA 또는 BBB가 된다. 각 인터벌에는 같은 종류의 태스크 하나만 들어가야하므로 AB_AB_AB가 되야한다
B가 인터벌안에 들어가던 마지막 태스크 뒤에 붙던 (task+all idles)안에 들어가고 idles에 태스크를 하나씩 채우면서 idles의 갯수를 줄여나가기 때문에 정답을 반환하는데는 상관없다.
