Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

Python으로 여러 사서함의 중요한 메일 라운드 로빈 방식으로 정렬하기

이번 글에서는 여러 개의 사서함에 흩어져 있는 메일을 하나로 모으는 프로그램을 Python으로 구현해 보겠습니다. 각 사서함은 문자열 리스트로 표현되며, 문자열은 다음 세 가지 유형 중 하나입니다.

  • "J" — 스팸 메일(Junk)
  • "P" — 개인 메일(Personal)
  • "W" — 업무 메일(Work)

목표는 첫 번째 사서함부터 시작하여 라운드 로빈(round-robin) 방식으로 각 사서함을 순회하면서 스팸 메일("J")은 제거하고, 나머지 중요한 메일만 하나의 리스트로 합쳐 반환하는 것입니다.

문제 예시

입력이 다음과 같다고 가정해 보겠습니다.

mailboxes = [["W", "P"], ["J", "P", "J"], ["W"]]

필터링 없이 라운드 로빈 순서대로 메일을 꺼내면 다음과 같습니다.

W → J → W → P → P → J

여기서 스팸 메일(J)을 제외하면 최종 결과는 아래와 같습니다.

["W", "W", "P", "P"]

풀이 접근 방법

이 문제는 다음 단계를 통해 해결할 수 있습니다.

  • n_mailboxes := 사서함의 총 개수
  • result := 결과를 저장할 새로운 리스트
  • counts := 각 사서함에서 현재까지 읽은 메일의 인덱스를 추적하는 크기 n_mailboxes의 리스트(0으로 초기화)
  • more := 반복 여부를 나타내는 플래그(True로 초기화)
  • more가 참인 동안 다음을 반복합니다.
    • more := False로 초기화
    • i를 0부터 n_mailboxes-1까지 순회하며
      • index := counts[i], mailbox := mailboxes[i]
      • 만약 index가 해당 사서함의 길이보다 작다면
        • more := True (아직 읽지 않은 메일이 있음)
        • counts[i] += 1 (읽은 메일 수 증가)
        • mail := mailbox[index] (현재 메일 가져오기)
        • 메일이 "J"가 아니라면 result의 끝에 추가
  • 모든 사서함을 다 읽었다면 result 반환

핵심 아이디어는 각 사서함마다 독립적인 포인터(counts)를 유지하면서, 한 바퀴씩 돌 때마다 아직 처리하지 않은 메일이 있는 사서함에서 하나씩 메일을 가져오는 것입니다. 더 이상 가져올 메일이 없으면 반복을 종료합니다.

Python 구현 코드

아래 코드를 통해 실제 동작을 확인해 보겠습니다.

class Solution:
    def solve(self, mailboxes):
        n_mailboxes = len(mailboxes)
        result = []
        counts = [0] * n_mailboxes
        more = True
        while more:
            more = False
            for i in range(n_mailboxes):
                index, mailbox = counts[i], mailboxes[i]
                if index < len(mailbox):
                    more = True
                    counts[i] += 1
                    mail = mailbox[index]
                    if mail != "J":
                        result.append(mail)
        return result

ob = Solution()
mailboxes = [["W", "P"], ["J", "P", "J"], ["W"]]
print(ob.solve(mailboxes))

입력

[["W", "P"], ["J", "P", "J"], ["W"]]

출력

['W', 'W', 'P', 'P']

동작 과정 상세 분석

코드가 실행되는 과정을 단계별로 살펴보면 다음과 같습니다.

  1. 1라운드: 첫 번째 사서함에서 "W"(결과에 추가), 두 번째 사서함에서 "J"(제외), 세 번째 사서함에서 "W"(결과에 추가)
  2. 2라운드: 첫 번째 사서함에서 "P"(추가), 두 번째 사서함에서 "P"(추가), 세 번째 사서함은 이미 비어 있으므로 건너뜀
  3. 3라운드: 첫 번째 사서함은 비어 있고, 두 번째 사서함의 마지막 메일 "J"는 제외됨
  4. 더 이상 읽을 메일이 없으므로 반복 종료 후 ["W", "W", "P", "P"] 반환

시간 복잡도

이 알고리즘은 전체 메일 수를 N, 사서함 개수를 M이라 할 때 O(N × M)의 시간 복잡도를 가집니다. 각 라운드마다 모든 사서함을 확인해야 하기 때문입니다. 만약 성능 최적화가 필요하다면, 빈 사서함을 미리 제거하거나 itertools.zip_longest 같은 도구를 활용해 라운드당 유효한 사서함만 순회하도록 개선할 수 있습니다.