99클럽(2기) - 코테스터디 24일차 TIL # Stack # Queue

LeetCode - 1700. Number of Students Unable to Eat Lunch

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.

---

 

1. 첫 번째 풀이

 

 시간복잡도 단축을 위해 deque을 사용했지만 타임아웃 에러가 발생했다. 

 

1) list -> deque 형변환

 시간복잡도를 줄여보려고 list에서 duque로 형변환해서 사용했다. deque은 'double ended queue'의 약어로 양쪽에서 데이터 입출력이 가능하다. list는 데이터 삽입 또는 삭제 시 O(n)의 시간복잡도를 가지지만 deque은 O(1)로 훨씬 효율적이다. 

 

2) sandwich가 없어질 때까지 학생이 선호하는 샌드위치 매핑 

 학생이 선호하는 샌드위치가 맞으면 sandwiches와 students에 popleft()를 사용해 현재 학생과 현재 샌드위치를 삭제한다. 학생이 선호하는 샌드위치가 아니면 맨 뒤로 가서 줄을 서듯이 맨 왼쪽 학생을 students에서 추출해 맨 오른쪽에 더한다.

 

3) 마지막까지 샌드위치를 못 먹은 학생 수 반환

 모든 sandwich가 소진될 때까지 남아있는 학생 수를 반환한다.

from collections import deque

class Solution:
    def countStudents(self, students: List[int], sandwiches: List[int]) -> int:
        students = deque(students) # deque으로 자료형 변환
        sandwitches = deque(sandwiches) # deque으로 자료형 변환
        count = 0
        
        while len(sandwiches) > 0:
            if students[0] == sandwiches[0]: # 학생이 선호하는 샌드위치이면
                sandwiches.popleft() # 맨 왼쪽 샌드위치 삭제
                students.popleft() # 맨 왼쪽 학생 삭제
            else:
                students.append(students.popleft) # 맨 왼쪽 요소를 추출해 맨 오른쪽에 더한다
        
        # 마지막까지 남은 학생 수 반환
        return len(students)

 

 

2. 두 번째 풀이

 

 효율적인 풀이가 없나.. 생각해봤다. 큐와 스택으로 푼 건 아니다. 각 타입의 샌드위치를 선호하는 학생 수를 세어 반환했다. 

 

1) 학생 선호도 카운트

 0 샌드위치를 좋아하는 학생과 1 샌드위치를 좋아하는 학생의 수를 세서 리스트 count 에 저장한다.  

 

2) sandwich가 없어질 때까지 학생이 선호하는 샌드위치 매핑 

 for문으로 샌드위치를 순회하면서 해당 타입의 샌드위치를 선호하는 학생이 있으면 카운트를 감소시키고, 없으면 break로 반복문을 빠져나온다. 

 

3) 마지막까지 남아있는 학생 수 반환 

 count 안에는 마지막까지 남아있는 학생의 수가 있다. 그런데 0을 선호하는 학생과 1을 선호하는 학생이 각각 몇 명인지 궁금한 것은 아니므로 count 안의 모든 학생의 수를 합쳐서 반환하면 된다. 

class Solution:
    def countStudents(self, students: List[int], sandwiches: List[int]) -> int:
        # 학생들의 선호도 카운트
        count = [students.count(0), students.count(1)]
        
        for sandwich in sandwiches:
            if count[sandwich] > 0:
                count[sandwich] -= 1
            else:
                # 더 이상 선호하는 학생이 없으면 종료
                break
        
        # 남아 있는 학생 수를 반환
        return sum(count)

 

 

3. 느낀점

 어떻게 하면 효율적으로 문제를 풀이할까 고민하면서 자료형에 국한되지 않는 풀이법을 생각해보게 된다.