Number of Students Unable to Eat Lunch

option 1: pikachu, option 2: pokeball

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.

 

Constraints:

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

학생들이 줄을 서있고, 샌드위치를 순서대로 받는데, 마음에 안들면 뒤로 가서 다시 받는 문제이다. 최종적으로 샌드위치를 못받은 학생의 수를 세는 문제이다. 처음에는 Queue를 이용한 해법으로 접근했다.

 

import java.util.*;
class Solution {
    public int countStudents(int[] students, int[] sandwiches) {
        Queue<Integer> queue = new LinkedList<>();
        int top = 0, count = 0;
        
        for (int s : students){
            queue.add(s);
        }
        
        while(!queue.isEmpty() && count != queue.size()){
            if(queue.peek() == sandwiches[top]){
                queue.poll();
                top++;
                count = 0;
            } else {
                queue.add(queue.poll());
                count++;
            }
        }
        
        return queue.size();
    }    
}

Array를 그대로 사용할수도 있지만, 코드가 복잡해지기 때문에 queue를 사용해 students를 카피한 후, while loop에서 앞에서부터 차례대로 기호가 샌드위치 순서와 맞는지 확인하고, 맞으면 두군데 모두 deque를 한 후, count를 0으로 해주고, 아니면 student queue에서만 deque를 해서, 맨 뒤에 넣은 후, 맞지않았던 것을 1회 카운트 해주는식이다. 만약 count가 연속적으로 늘어나서 queue의 사이즈와 같아진다면, 그것은 이제 더이상 학생을 만족시킬 샌드위치가 남아있지 않음을 의미한다. 왜냐하면 맨 위에 top에 있는 샌드위치를 아무도 가져가지 않았기 때문이다.

 

이 해법은 O(N)의 space를 사용했고, O(N)의 시간이 소요된다.

속도나 스페이스면에서 아주 좋은 성과를 내지는 못했다.

 

 

더나은 해법도 있었다.

    public int countStudents(int[] students, int[] sandwiches) {
        int count[] = {0, 0};
        int slen = students.length;
        int i;
        for (int s : students){
            count[s]++;
        }
        for (i = 0; i < slen && count[sandwiches[i]] > 0; i++){
            count[sandwiches[i]]--;
        }
        return slen - i;
    }

사실 Queue를 사용할 필요 없이, 샌드위치 선호도를 조사한 후, 샌드위치가 먼저 떨어지든, 한 샌드위치를 선호하는 학생이 먼저 살아지든지 그 조건에 충족할때까지 count에서 빼주면 된다. 이후, 만약 샌드위치를 다 세지 못했다면 차이를 리턴하고, 모두 소진했다면 0이 나오는 방식이다. 시간은 O(N)이 쓰이지만, Space는 O(1)이 쓰이는 아주 효율적인 방법이다. 속도면에서 아주 우수했다.

 

 

 

 

 

https://leetcode.com/problems/number-of-students-unable-to-eat-lunch/

Number of Students Unable to Eat Lunch - LeetCode