Number of Students Unable to Eat Lunch (deque)

LeetCode의 Number of Students Unable to Eat Lunch 문제다.

Number of Students Unable to Eat Lunch - LeetCode

별로 어렵지 않은 문제지만 collections 모듈의 Counter 클래스를 활용하는 풀이가 있어 적어본다. 문제는 다음과 같다.

• 학생들은 선호하는 샌드위치 모양이 있다. 이는 각각 0, 1로 나타낸다.

• 학생들을 위해 준비된 샌드위치들이 있다. 이들 역시 모양에 따라 0, 1로 나타낸다.

• 학생, 정확히는 학생들이 선호하는 샌드위치와 준비된 샌드위치는 동일한 크기의 배열로 제공된다.

• 샌드위치 배열은 스택처럼 동작한다.

• 학생 배열은 큐처럼 동작한다.

• 학생 배열(큐)에서 꺼낸 선호하는 샌드위치가 샌드위치 배열(스택)에서 제공하는 샌드위치가 아닐 경우 다시 큐에 삽입한다.

• 이 과정을 반복했을 때 샌드위치를 먹을 수 없는 학생의 수는 몇 명인가?

좀 길어 보이지만 간단하다. 학생 배열은 [1,0,0,1]이고 샌드위치 배열이 [0,1,0,1]이라면 학생 배열의 맨 앞에서 꺼낸 학생은 1 샌드위치를 선호한다. 하지만 샌드위치 배열의 맨 앞에서는 0 샌드위치를 제공하고 있기 때문에 학생은 다시 배열에 삽입되어 학생 배열은 [0,0,1,1]이 된다.

 

그리고 다시 학생 배열에서 꺼낸 학생은 0 샌드위치를 선호하기 때문에 다시 삽입되지 않으며 샌드위치 역시 배열에서 삭제된다. 그래서 학생 배열과 샌드위치 배열은 각각 [0,1,1]과 [1,0,1]이 된다. 동일하게 선호하는 샌드위치가 안 맞기 때문에 학생 배열은 [1,1,0]이 되고 이번에는 맞기 때문에 각각 [1,0]과 [0,1]이 된다. 그리고 반복해서 샌드위치를 나눠주다 보면 전부 다 나눠줄 수 있기 때문에 해답은 0명이 된다.

 

반대로 학생 배열이 [1,0,0,1], 샌드위치 배열이 [0,1,1,1]이라면 어떨까? 이는 결과적으로 1명에게 샌드위치를 나눠줄 수 없다. 왜냐면 학생 배열이 [0,0,1,1]이 돼서 샌드위치 배열에서 0 샌드위치를 빼가면 [0,1,1]과 [1,1,1]이 되며 0 샌드위치를 선호하는 학생이 뒤로 가서 [1,1,0]과 [1,1,1]이 되면 최종적으로 학생 배열에는 [0], 샌드위치 배열에는 [1]이 남기 때문이다. 그래서 1명의 학생이 샌드위치를 받을 수 없다.

 

이를 기반으로 구현한 코드는 다음과 같다.

import collections


class Solution:
    def countStudents(self, students: List[int], sandwiches: List[int]) -> int:
        students_deque = collections.deque(students)
        sandwiches_deque = collections.deque(sandwiches)
        
        # 학생 배열에서 샌드위치를 받을 학생이 선호하는 샌드위치가 샌드위치 배열에 있는가?
        while len(sandwiches_deque) > 0 and students_deque.count(sandwiches_deque[0]) > 0:
            # 선호하는 샌드위치를 받았다면 배열에서 제거.
            if students_deque[0] == sandwiches_deque[0]:
                students_deque.popleft()
                sandwiches_deque.popleft()
            # 받지 못했다면 대기열 뒤로 삽입.
            else:
                students_deque.append(students_deque.popleft())
                
        # 몇 명이나 샌드위치를 수령하지 못했는가?
        return len(students_deque)

시간문제도 있고 해서 파이썬의 리스트는 큐(Queue) 용도로 사용하지 말라고 했기 때문에 collections 모듈의 deque 클래스를 활용하여 풀었는데 성능(속도)은 상위 53% 정도로 썩 만족스럽지 않았다. 아마 deque 클래스를 활용해서 그런 것일까? 더 좋은 성능의 풀이를 찾아보니 다음처럼 Counter 클래스를 활용하는 것을 볼 수 있었다.

class Solution:
    def countStudents(self, students: List[int], sandwiches: List[int]) -> int:
        count = Counter(students)
        n = len(students)
        for ind, val in enumerate(sandwiches):
            if count.get(val, 0) > 0:
                count[val] -= 1
            else:
                break
        return sum(count.values())

즉 학생들이 선호하는 0 샌드위치, 1 샌드위치의 개수를 Counter 클래스로 측정해서 count 변수에 담아두고 샌드위치 배열을 돌면서 선호하는 샌드위치가 있으면 해당 학생에게 나눠줬다고 가정하고 개수를 하나씩 줄이는 방법이었다.

 

특히 지금 나눠줄 샌드위치를 선호하는 학생이 없다면 학생 배열에 있는 모든 학생들은 샌드위치를 받을 수 없기 때문에 반복문을 탈출하는 로직이 핵심인 것 같다. 예를 들어 학생이 [0,1,1,1,1]이고 샌드위치가 [0,0,1,1,1]이라면 맨 처음 학생에게 나눠주고 [1,1,1,1]과 [0,1,1,1]이 된다. 그리고 지금 나눠줄 0 샌드위치를 선호하는 학생이 없기 때문에 학생 배열에 있는 아무도 이 0 샌드위치를 가져가고 뒤에 있는 1 샌드위치 3개를 받을 방법이 없다.

 

샌드위치를 못 받은 학생들의 수를 세야 하기 때문에 샌드위치 배열을 반복문으로 돈다는 점 역시 중요하다.