[파이썬 알고리즘 인터뷰][그리디] 태스크 스케줄러

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

n개 안에 겹치는 문자가 없도록 배열, 불가능할 경우 "idle"을 삽입하여 최소 길이 출력

 

책에서 구현된 코드

import collections
from typing import List


class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        counter = collections.Counter(tasks)
        result = 0

        while True:
            sub_count = 0
            # 개수 순 추출
            for task, _ in counter.most_common(n + 1):
                sub_count += 1
                result += 1

                counter.subtract(task)
                # 0 이하인 아이템을 목록에서 완전히 제거
                counter += collections.Counter()

            if not counter:
                break

            result += n - sub_count + 1

        return result

 

기억해야할 기법

• 문제 접근
  
  • 서로 다른 n+1개를 뽑을 경우, n개가 겹치지 않음
• Counter 메서드
  • substract
    - 1개를 뺀다
  • counter += collections.Counter()
    - 0인 목록을 제거한다

 

내가 구현한 코드

None

• 로직을 얼추 생각해내는데 코드 설계가 내맘대로 되지 않는다
• 그리디 알고리즘 문제는 정말 많이 풀어봐야겠다