파이썬으로 선호하는 음식 패킷을 받지 못하는 사람의 수 구하기

어떤 컨퍼런스에 두 가지 유형의 사람들이 있다고 가정해 보겠습니다. 한 유형은 채식(vegetarian) 식사를 선호하고, 다른 유형은 비채식(non-vegetarian) 식사를 선호합니다. 그런데 음식 패킷의 수는 제한되어 있어서, 채식주의자가 비채식 패킷을 받게 되거나 그 반대의 경우에는 해당 패킷을 거절하고 자신이 원하는 패킷을 받을 때까지 기다립니다.

여기서 두 가지 유형의 패킷과 사람은 각각 0 = 채식, 1 = 비채식으로 표현합니다. 프로그램에는 두 개의 배열이 주어집니다. 하나는 0과 1로 표시된 n개의 음식 패킷 목록이고, 다른 하나는 m명의 사람들이 줄을 선 대기열이며 각 사람의 선호도 역시 0과 1로 나타냅니다. 만약 어떤 사람이 선호하는 패킷을 받지 못하면, 그 사람은 대기열 맨 뒤로 다시 들어가 자신에게 맞는 패킷을 기다리게 됩니다.

결국 우리가 구해야 하는 것은 음식 패킷을 받지 못한 채 남겨지는 사람의 수입니다. 이를 통해 부족한 패킷을 얼마나 추가로 준비해야 하는지 파악할 수 있습니다.

문제 예시

예를 들어 입력이 다음과 같다고 해보겠습니다.

people = [0,1,1,0]
packets = [0, 1, 0, 0]

이 경우 출력은 1입니다. 비채식을 선호하는 사람은 두 명인데, 비채식 패킷은 하나뿐입니다. 줄에서 비채식을 선호하는 첫 번째 사람이 그 패킷을 가져가고, 나머지 한 사람은 더 이상 비채식 패킷이 없어 끝까지 기다리게 됩니다. 따라서 결과는 1명입니다.

해결 접근 방법

이 문제는 실제로 대기열을 하나씩 시뮬레이션할 필요 없이, 선호 유형별 인원수와 패킷 수를 카운팅하는 방식으로 효율적으로 해결할 수 있습니다. 단계별 과정은 다음과 같습니다.

길이가 2인 리스트 temp_arr를 [0, 0]으로 초기화합니다. (인덱스 0은 채식, 인덱스 1은 비채식)
people 배열을 순회하며 각 사람의 선호 유형에 해당하는 카운트를 1씩 증가시킵니다.
포인터 k를 0으로 초기화합니다.
k가 패킷 배열의 길이보다 작은 동안 반복합니다.
- 현재 패킷 유형 packets[k]에 해당하는 대기 인원이 0보다 많으면, 해당 카운트를 1 감소시키고 다음 패킷으로 넘어갑니다.
- 그렇지 않다면, 더 이상 현재 패킷을 받을 사람이 없다는 뜻이므로 반복문을 종료합니다.
최종적으로 len(packets) - k를 반환합니다. 이 값이 배분되지 못한 패킷, 즉 음식을 받지 못한 사람의 수입니다.

핵심 아이디어는 패킷 배열을 앞에서부터 순서대로 처리할 때, 각 패킷 유형을 원하는 사람이 남아 있으면 계속 배분하고, 원하는 사람이 없어지는 순간 그 이후의 모든 패킷도 배분할 수 없다는 점입니다. 대기열에서 사람들이 뒤로 다시 들어가더라도 결국 패킷 순서는 변하지 않기 때문에, 카운팅만으로 정답을 구할 수 있습니다.

파이썬 구현 코드

아래는 위 로직을 파이썬으로 구현한 예제입니다.

def solve(people, packets):
    temp_arr = [0, 0]
    for person in people:
        temp_arr[person] += 1
    k = 0
    while k < len(packets):
        if temp_arr[packets[k]] > 0:
            temp_arr[packets[k]] -= 1
        else:
            break
        k += 1
    return len(packets) - k

print(solve([0,1,1,0], [0, 1, 0, 0]))

입력

[0,1,1,0], [0, 1, 0, 0]

출력

복잡도 분석

이 알고리즘은 사람 배열을 한 번 순회하고(O(m)), 패킷 배열도 최대 한 번 순회하므로(O(n)) 전체 시간 복잡도는 O(n + m)입니다. 추가로 사용하는 공간은 길이 2짜리 리스트뿐이므로 공간 복잡도는 O(1)로 매우 효율적입니다. 실제 대기열 회전을 시뮬레이션하는 방식(최악의 경우 O(n × m))보다 훨씬 빠르게 동작합니다.