99클럽 코테 스터디 24일차 1700. Number of Students Unable to Eat Lunch

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

 

문제 설명

학교 급식 시간에 학생들은 일렬로 줄을 섭니다. 각 학생은 선호하는 두 가지 종류의 샌드위치 중 하나를 고를 수 있습니다: 원형 샌드위치와 네모난 샌드위치입니다. 각각의 학생은 특정 종류의 샌드위치만 선호합니다. 또한, 급식 테이블 위에는 같은 수의 원형 샌드위치와 네모난 샌드위치가 있습니다.

학생들은 다음과 같은 규칙에 따라 샌드위치를 받습니다:

• 줄의 맨 앞에 있는 학생은 테이블 위의 맨 위에 있는 샌드위치를 확인합니다.
• 학생이 선호하는 종류의 샌드위치라면 그 샌드위치를 가져가고 줄을 떠납니다.
• 만약 그렇지 않으면, 학생은 줄의 맨 뒤로 이동합니다.
• 이 과정은 더 이상 학생들이 원하는 샌드위치를 받을 수 없을 때까지 반복됩니다.

이때, 샌드위치를 받을 수 없는 학생의 수를 구하시오.

입력

• students: 학생들이 선호하는 샌드위치의 종류를 나타내는 정수 배열입니다. 각 요소는 0 또는 1입니다.
  • 0은 원형 샌드위치를 선호하는 학생을 의미합니다.
  • 1은 네모난 샌드위치를 선호하는 학생을 의미합니다.
• sandwiches: 테이블 위의 샌드위치의 종류를 나타내는 정수 배열입니다. 각 요소는 0 또는 1입니다.
  • 0은 원형 샌드위치를 의미합니다.
  • 1은 네모난 샌드위치를 의미합니다.

출력

• students 배열에 남아있는, 샌드위치를 받을 수 없는 학생의 수를 반환합니다.

 

 

풀이

 

class Solution:
    def countStudents(self, students: List[int], sandwiches: List[int]) -> int:
        #1 학생과 샌드위치를 덱으로 변환한다
        #2 학생이 현재 샌드위치를 좋아하는지 반복문을 통해 검증한다.
        #3 검증 과정에서 덱을 활용하고, 안맞는 학생이 전체학생 수인경우 반복종료한다.

        #1 덱으로 변환
        students = deque(students)
        sandwiches = deque(sandwiches)

        # 샌드위치를 거부한 학생의 수
        rejected_counts=0

        # 2 학생이 샌드위치를 좋아하는지 검증
        while students:
            # 샌드위치를 좋아하는 경우
            if students[0] == sandwiches[0]:
                # 좋아하는 경우, 샌드위치와 학생에서 제거한다
                students.popleft()
                sandwiches.popleft()
                # 거부 학생 수 초기화
                rejected_counts = 0

            else:
                # 제일 앞에 있는 학생 -> 맨 뒤로 보내야하므로
                # 학생 deque 에서 왼쪽 학생을 제거 후, 오른쪽에 다시 추가한다.
                students.append(students.popleft())
                rejected_counts += 1

            # 3 안 맞는 학생 = 모든 학생이 된 경우
            if rejected_counts == len(students):
                # while문 반복 종료
                break
        #남은 학생수 반환
        return len(students)