[leetcode] Number of Students Unable to Eat Lunch

문제

• 문제 링크
• 배열 students와 배열 sandwiches가 주어진다. sandwiches에는 샌드위치 종류인 0과 1이 들어가 있다. students에는 각 학생이 먹고 싶은 샌드위치 종류가 들어가 있다.
• 학생은 아래 순서에 따라 샌드위치를 가져간다.
  • students 배열 맨 앞에 있는 학생이 먹고 싶은 샌드위치를 확인한다.
  • 먹고 싶은 샌드위치가 sandwiches 맨 앞에 있다면 학생은 샌드위치를 가져가고 떠난다.
  • 만약 먹고 싶은 샌드위치가 맨 앞에 없다면 students 배열 맨 뒤에 가서 다시 차례를 기다린다.
• 위 단계를 반복하다가 아무도 맨 앞에 있는 샌드위치를 가져가지 못하는 경우가 생긴다. 이때 샌드위치를 가져가지 못한 총 학생의 수를 구해야 한다.
• 제약 조건
  • students.length == sandwiches.length
  • 배열 길이: 1 <= students.length, sandwiches.length <= 100
  • sandwiches[i] is 0 or 1
  • students[i] is 0 or 1

풀이

풀기 전

• 문제에 큐랑 스택이랑 단어가 나와서 그대로 구현하려는 충동이 들지만 예시를 생각하며 고민해보면 비효율적이라는 생각이 든다.
• 아무도 샌드위치를 가져가지 못하는 상황을 생각하면 쉽게 풀린다. sandwiches 배열 맨 앞에 있는 샌드위치가 0일 때, students 배열 안에 0인 샌드위치를 원하는 학생이 한 명이라도 있다면 언젠가 샌드위치를 가져간다. 반대로, students 배열 안에 0인 샌드위치를 원하는 학생이 아무도 없다면 샌드위치는 아무도 가져가지 못한다. 이때 남아있는 학생들은 모두 샌드위치를 가져가지 못한다.
• 맨 앞에 있는 샌드위치가 1인 경우에도 뒤집어서 생각하면 된다.

코드

class Solution {
    public int countStudents(int[] students, int[] sandwiches) {
        int[] wants = {0, 0};  // 샌드위치 0, 1을 원하는 학생 수를 저장한다.
        for (int s : students) {
            wants[s]++;
        }
        
        for (int s : sandwiches) {
        	// 샌드위치가 0인데 0을 원하는 학생이 없으면 샌드위치 1을 원하는 학생 수를 반환한다.
            if (s == 0 && wants[0] == 0)  
                return wants[1];
                
            // 샌드위치가 1인데 1을 원하는 학생이 없으면 샌드위치 0을 원하는 학생 수를 반환한다.
            if (s == 1 && wants[1] == 0)
                return wants[0];
                
            // 샌드위치를 원하는 학생이 있으면 학생 수를 줄인다.
            wants[s]--;
        }
        return 0;
    }
}

푼 후

• 조금만 생각해보면 쉽게 풀리는 문제였다.
• students와 sandwiches를 한 번씩 순회하기 때문에 시간 복잡도는 O(students.length)이다. 학생 수를 집계하는 배열 길이는 2이기 때문에 공간 복잡도는 O(1)이다.