[LeetCode] 1700. Number of Students Unable to Eat Lunch (Daily Question)

문제

---

The school cafeteria offers circular and square sandwiches at lunch break, referred to by numbers 0 and 1 respectively. All students stand in a queue. Each student either prefers square or circular sandwiches.

The number of sandwiches in the cafeteria is equal to the number of students. The sandwiches are placed in a stack. At each step:
    - If the student at the front of the queue prefers the sandwich on the top of the stack, they will take it and leave the queue.
    - Otherwise, they will leave it and go to the queue's end.

This continues until none of the queue students want to take the top sandwich and are thus unable to eat.
You are given two integer arrays students and sandwiches where sandwiches[i] is the type of the i​​​​​​th sandwich in the stack (i = 0 is the top of the stack) and students[j] is the preference of the j​​​​​​th student in the initial queue (j = 0 is the front of the queue). Return the number of students that are unable to eat.

 

둥근샌드위치는 0, 사각샌드위치는 1을 의미한다.

students는 각 학생들이 원하는 샌드위치종류가 배급을 받기위해 줄서있는 순서로 주어지고,

sandwitches는 배급하는 샌드위치종류가 순서대로 주어진다.

 

이번에 배급하는 샌드위치의 종류가 맨 앞의 학생이 원하는 종류가 아닌 경우 맨 뒤로가서 다시 줄을 선다.

원하는 종류라면 해당 샌드위치를 가져가서 맛있게 먹는다.

 

Example 1:
Input: students = [1,1,0,0], sandwiches = [0,1,0,1]
Output: 0
Explanation:
- Front student leaves the top sandwich and returns to the end of the line making students = [1,0,0,1].
- Front student leaves the top sandwich and returns to the end of the line making students = [0,0,1,1].
- Front student takes the top sandwich and leaves the line making students = [0,1,1] and sandwiches = [1,0,1].
- Front student leaves the top sandwich and returns to the end of the line making students = [1,1,0].
- Front student takes the top sandwich and leaves the line making students = [1,0] and sandwiches = [0,1].
- Front student leaves the top sandwich and returns to the end of the line making students = [0,1].
- Front student takes the top sandwich and leaves the line making students = [1] and sandwiches = [1].
- Front student takes the top sandwich and leaves the line making students = [] and sandwiches = [].
Hence all students are able to eat.

Example 2:
Input: students = [1,1,1,0,0,1], sandwiches = [1,0,0,0,1,1]
Output: 3

 

---

 

풀이

---

아이디어

맨 앞의 학생이 맨 뒤로 가는 동작에 있어서 코스트가 전혀 없기 때문에 학생의 순서를 고려하지 않아도 된다.

따라서 줄을 서는 것이 아닌, 이번에 배급하는 샌드위치를 먹을 사람이 있다면 배급해주는 식으로 생각해도 된다.

 

코드

class Solution:
    def countStudents(self, students: List[int], sandwiches: List[int]) -> int:
        # 모양별 샌드위치를 원하는 학생의 수 
        circular_cnt = sum(students)
        square_cnt = len(students) - circular_cnt

        # 가장 위에 있는 샌드위치를 원하는 학생이 없을 때까지 샌드위치를 차례대로 배급
        eat_cnt = 0
        for sandwich in sandwiches:
            if sandwich: circular_cnt -= 1
            else: square_cnt -= 1

            if circular_cnt * square_cnt < 0:
                return len(students) - eat_cnt

            eat_cnt += 1

        return 0

 

---

 

후기

---

난이도

이런 방식의 아이디어를 바로 떠올리긴 쉽지 않을 수 있지만,

다른 풀이방식도 존재하기 때문에 문제만 이해하면 어떻게 풀지는 쉽게 파악할 수 있다.

구현도 쉽게 할 수 있다.

 

다른 풀이

맨 앞의 학생을 맨 뒤로 보내며 문제 그대로 구현하여 풀 수 있다.