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

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

Leetcode - Number of Students Unable to Eat Lunch

문제 유형 : 스택, 큐

문제 난이도 : Easy

 

문제

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로 나타내진다.

샌드위치의 수는 학생들의 수와 같다. 샌드위치는 쌓여있다.

학생들은 줄을 서서 샌드위치를 받는다.

 

만약 맨 앞의 학생이 샌드위치들의 맨위에 있는 종류를 선호하지 않는다면, 맨 뒤로 돌아간다.

만약 선호하는 샌드위치라면, 샌드위치를 받는다.

 

배열로 샌드위치의 선호와 샌드위치가 주어집니다. 샌드위치의 0번인덱스가 맨 위에 있다는 뜻이고, 선호의 0번 인덱스가 줄의 맨 앞이다.

샌드위치를 못 먹는 학생들의 수를 구하시오.

 

풀이

학생은 큐에, 샌드위치는 역순으로 스택에 저장시킨다.

 

문제 그대로 구현해주면 된다.

큐의 맨 앞이 스택의 맨 위와 다르다면, 큐의 맨 앞을 뒤로 보내고, 같다면 스택과 큐를 그냥 pop 하면 된다.

만약 큐의 크기만큼 반복하고도 샌드위치를 가져가지 못했다면, 반복을 마친다.

 

큐의 크기만큼 반환한다.

 

코드

C++

class Solution {
public:
    int countStudents(vector<int>& students, vector<int>& sandwiches) {
        queue<int> q;
        stack<int> st;

        for(const auto student : students) {
            q.push(student);
        }

        for(int i = sandwiches.size()-1; i >= 0; i--) {
            st.push(sandwiches[i]);
        }

        while(!q.empty()) {
            bool taken = false;
            for(int i = 0; i < q.size(); i++) {
                if(q.front() == st.top()) {
                    st.pop();
                    taken = true;
                } else {
                    q.push(q.front());
                }
                q.pop();

                
            }
            if(!taken) break;
        }

        return q.size();
    }
};