[2024] day 100. Leetcode 1700. Number of Students Unable to Eat Lunch

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 4월 8일 (월)
Leetcode daily problem

1700. Number of Students Unable to Eat Lunch

https://leetcode.com/problems/number-of-students-unable-to-eat-lunch/?envType=daily-question&envId=2024-04-08

Problem

학교 구내식당에서는 점심 시간에 원형 샌드위치와 사각형 샌드위치를 제공하며 각각 숫자 0과 1로 표시한다. 각 학생은 정사각형 또는 원형 샌드위치를 선호한다.

구내식당의 샌드위치 수는 학생 수와 같고, 샌드위치는 스택에 존재한다.
모든 학생들이 샌드위치를 먹을 수 있는지 확인하는 것이고, 먹을 수 없는 학생의 수를 반환하는 것이다.

• 대기열의 맨 앞에 있는 학생이 스택 맨 위의 샌드위치를 선호한다면, 그 학생은 그것을 가져가고 대기열에서 나간다.
• 그렇지 않다면, 그 학생은 그것을 놔두고 대기열의 끝으로 이동한다.
• 이러한 과정은 대기열의 모든 학생이 맨 위의 샌드위치를 가져가고 싶어하지 않고 먹을 수 없을 때까지 계속된다.

students와 sandwiches 두 개의 정수 배열이 주어지고, 여기서 sandwiches[i]는 스택에서 i번째 샌드위치의 유형을 나타내며 (i = 0은 스택의 맨 위를 의미), students[j]는 초기 대기열에서 j번째 학생의 선호를 나타낸다. (j = 0은 대기열의 맨 앞을 의미). 샌드위치를 먹지 못한 학생의 수를 반환한다.

Solution

stack, queue

학생들과 샌드위치의 정보를 확인하면서 각 학생이 선호하는 샌드위치가 줄 서 있는 샌드위치 중에 있는지 확인한다. 만약 존재한다면 해당 샌드위치를 줄에서 제거한다.
만약 샌드위치가 없다면 학생은 샌드위치를 먹을 수 없는 것으로 판단한다.
마지막으로 샌드위치를 받지 못한 학생의 수를 반환한다.

Code

Complexicity

시간 복잡도

공간 복잡도