[LeetCode] 1700. Number of Students Unable to Eat Lunch

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:

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

 

Constraints:

• 1 <= students.length, sandwiches.length <= 100
• students.length == sandwiches.length
• sandwiches[i] is 0 or 1.
• students[i] is 0 or 1.

---

풀이코드

class Solution {
    public int countStudents(int[] students, int[] sandwiches) {
        Queue<Integer> std = new LinkedList<>();
        Queue<Integer> snd = new LinkedList<>();

        for(int i=0; i<students.length; i++) {
            std.add(students[i]);
            snd.add(sandwiches[i]);
        }

        while(std.contains(snd.peek())) {
            int frontStd = std.poll();
            if(frontStd == snd.peek()) {
                snd.poll();
            } else {
                std.add(frontStd);
            }
        }

        return std.size();

    }
}

---

풀이방법

학생, 샌드위치라는 2개의 배열을 주고 샌드위치를 먹지 못한 학생이 몇명인지 return 을 해줘야하는 문제이다.

문제의 조건은 학생과 샌드위치를 비교하여 동일하면 학생이 샌드위치를 먹고, 일치하지않으면 학생은 제일 뒤 순번으로 이동한다. 그렇게 반복하여 샌드위치를 먹는다.

1. 학생과 샌드위치 2개의 Queue를 선언해준다.
2. 2개의 큐에 값을 모두 담는다.
3. while 문을 실행하는데 조건은 현재 최상위에 있는 샌드위치가 학생 큐에 포함되어있어야한다.
   이유는 현재 최상위 샌드위치가 학생 큐에 포함되있지않다면 학생 큐에서 계속돌아도 학생은 샌드위치를 먹을수없기때문이다.