LinkedList (Queue): 1700. Number of Students Unable to Eat Lunch ★

1700. Number of Students Unable to Eat Lunch

 

https://youtu.be/d_cvtFwnOZg?si=KkHPkdE6CuKThQq4

 

class Solution:
    def countStudents(self, students: List[int], sandwiches: List[int]) -> int:
        # 전체 학생 수 (Total number of students)
        res = len(students)
        
        # 학생들의 선호도를 카운트하기 위한 Counter 생성
        # Create a Counter to count the preferences of students.
        # 예: students = [1, 1, 0, 0] → cnt = {1: 2, 0: 2}
        cnt = Counter(students)
        
        # 샌드위치 리스트를 순서대로 처리 (Process each sandwich in order)
        for s in sandwiches:
            # 만약 현재 샌드위치를 원하는 학생이 있다면
            # If there is at least one student who prefers the current sandwich type 's':
            if cnt[s] > 0:
                # 학생 한 명이 샌드위치를 먹으므로 학생 수 감소
                # A student takes the sandwich, so decrease the count of students.
                res -= 1
                
                # 해당 선호도를 가진 학생의 수를 1 감소
                # Decrease the count of students who prefer sandwich type 's'.
                cnt[s] -= 1
            else:
                # 현재 샌드위치를 원하는 학생이 없다면, 더 이상 진행할 수 없으므로
                # return 현재 남은 학생 수.
                # If no student prefers the current sandwich, break and return the number of remaining students.
                return res

        # 모든 샌드위치를 처리한 후 남은 학생 수 반환
        # After processing all sandwiches, return the remaining student count.
        return res

 

이 코드는 학생들의 선호도와 샌드위치의 종류에 따라 학생들이 먹을 수 없는 인원의 수를 계산하는 문제를 해결하는 방법입니다. 문제의 핵심은 학생들이 선호하는 순서대로 샌드위치가 주어질 때,

더 이상 원하는 샌드위치를 먹을 수 없는 상황이 언제 발생하는지를 판단하는 것입니다.

 

 

결론

• 핵심 아이디어: 학생들의 선호도를 카운터(Counter)로 관리하면서, 샌드위치가 제공될 때마다 해당 선호도를 감소시킵니다.
• 조기 종료: 만약 현재 제공하려는 샌드위치를 선호하는 학생이 없다면, 즉시 남은 학생 수를 반환합니다.
• 시간 복잡도: 리스트를 한 번 순회하므로 O(n) 시간 내에 해결됩니다.