# 資訊

:::info
- Question: 1700. Number of Students Unable to Eat Lunch
- From: Leetcode Daily Challenge 2024.04.08
- Difficulty: Easy
:::

---

# 目錄

:::info
[TOC]
:::

---

# 題目

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.

> Example 1:
:::success
* 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:
:::success
* Input: `students = [1,1,1,0,0,1]`, `sandwiches = [1,0,0,0,1,1]`
* Output: 3
:::

> Constraints:
:::success
* 1 <= `students.length`,` sandwiches.length` <= 100
* `students.length` == `sandwiches.length`
* `sandwiches[i]` is 0 or 1.
* `students[i]` is 0 or 1.
:::

---

# 解法

## 概念

多了 queue 的概念進來，不過就是取前後而已，對 python 來說都一樣叫做 pop

其實這題就是去思考如何模擬這個情況。基本上只有在 `students[0] == sanswiches[0]` 的時候才會發生 take，不然基本上都是 `students[0]` 去後面排隊，也就是 `pop` 然後 `push` 的過程。而我終止條件判斷方法是當 `students` 全部都是 0 或 1，而 `sandwiches[0]` 是跟 `students` 相反的元素時就該停止，不過這層判斷我是透過 `n0`、`n1` 這兩個變數判斷，原因只是我不想一直拿 `len(students)` 出來，剛好想到用這個方法只要最前面存取一次就可以了，不過那一兩次的 $O(n)$ 還是跑不掉。。

複雜度部分看起來應該是差不多這樣了，測資 100 其實很小

結論：Python 的 -1 真的很讚！

## 程式碼

class Solution:
    def countStudents(self, students: List[int], sandwiches: List[int]) -> int:
        n0 = students.count(0)
        n1 = students.count(1)
        while True:
            if students[0] == sandwiches[0]:
                tmp = students.pop(0)
                sandwiches.pop(0)
                if tmp == 0:
                    n0 -= 1
                else:
                    n1 -= 1
            else:
                tmp = students.pop(0)
                students.append(tmp)
            
            if ( not sandwiches ) or ( sandwiches[0] == 0 and n0 == 0 ) or ( sandwiches[0] == 1 and n1 == 0 ):
                break
        return n0 + n1

---

# 複雜度

## 時間複雜度

主要是在最前面計算 `n0`, `n1` 時花了 $O(2n)$，而後面模擬部分最差也會是 $O(n)$，整體算是 $O(n)$

嘛。。模擬部分最差也會是 $O(n)$ 這句話可能要想一想


## 空間複雜度

這就沒意外是 $O(1)$ 了！