[99클럽 코테 스터디] 23일차 TIL - 스택/큐, Number of Students Unable to Eat Lunch

[23일차] 스택/큐

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

* 번역: 학교 카페테리아는 점심시간에 원형과 정사각형 샌드위치를 제공합니다. 이 샌드위치는 각각 0번과 1번으로 구분됩니다. 모든 학생들은 줄을 서 있으며, 각 학생은 원형 샌드위치나 정사각형 샌드위치를 선호합니다.

샌드위치의 수는 학생 수와 같습니다. 샌드위치는 스택에 쌓여 있습니다. 각 단계에서 다음과 같은 일이 일어납니다:

1. 줄의 맨 앞에 있는 학생이 스택 맨 위에 있는 샌드위치를 선호하면, 그 샌드위치를 가져가서 줄을 떠납니다.
2. 그렇지 않으면, 그 학생은 샌드위치를 가져가지 않고 줄의 끝으로 갑니다.
3. 이런 과정이 반복되다가 더 이상 줄에 있는 학생들이 스택 맨 위의 샌드위치를 원하지 않게 되면, 그들은 샌드위치를 먹을 수 없게 됩니다.

두 개의 정수 배열 students와 sandwiches가 주어집니다. sandwiches[i]는 스택에서 i번째 샌드위치의 종류를 나타내며 (i = 0은 스택의 맨 위에 있는 샌드위치입니다), students[j]는 초기 줄에서 j번째 학생의 선호도를 나타냅니다 (j = 0은 줄의 맨 앞에 있는 학생입니다).

먹을 수 없는 학생의 수를 반환하세요.

My Solution

반복문을 통해 count변수를 세어주었다. 모두가 먹지 않는 이상, 즉 students 큐가 비지 않는 이상 반복하도록 while문을 짰다. 1회 반복에서는 가장 앞에 있는 학생 한 명씩 검사하고, 못 먹으면 맨 앞 학생이 다시 맨 뒤로 가야 하므로 pop하여, 다시 push(append())하고 count 변수를 1 증가 시킨다.

 

첫 번째 원소를 꺼내는 pop(0)과 맨 뒤에 덧붙이는 append를 효율적으로 처리할 수 있는 deque 자료형을 사용하였다.

from collections import deque

class Solution:
    def countStudents(self, students: List[int], sandwiches: List[int]) -> int:
        students = deque(students)
        sandwiches = deque(sandwiches)
        count = 0 # 못 먹는 사람 수

        while students:
            if students[0] == sandwiches[0]:
                students.popleft()
                sandwiches.popleft()
                count = 0 # 학생이 샌드위치 가져가면 리셋
            else:
                students.append(students.popleft())
                count += 1
            
            # 모두가 못 먹으면
            if count == len(students):
                return len(students)
        
        return 0

Solution

문제를 문자 그대로 구현하려고 해서 위의 코드는 꽤 복잡했다. 그러나 문제에서 원하는 답을 내기 위해서는 아래와 같이 단순히 해결도 가능하다.

def countStu(stu,sand):
	# 샌드위치에 원소가 남았다면
    while sand:
		# 맨 앞 샌드위치가 학생 목록 중 있다면
        if sand[0] in stu:
			# 학생 목록에서 원소 제거
            stu.remove(sand[0])
			# 샌드위치 목록에서 맨 앞 원소 제거
            sand.pop(0)
		# 첫 원소가 학생 목록에 없다면 (남은 학생 아무도 원하지 않음) 반복 종료
        else:break
	# 학생들이 먹을 수 있는 모든 샌드위치를 없애고 나서 남은 샌드위치의 길이가
    # 곧 먹을 수 없는 샌드위치의 갯수다.
    return len(sand)

맨 앞의 샌드위치 (sandwiches[0])를 원하는 학생들이 있는지 검사하고, 있다면 그 학생을 제거한다.

나다어

나는 다음에 어떻게 풀까

오답노트. 초기에 작성했던 코드는 아래와 같았다. 계속해서 순회하되, 모두가 가져갔거나 현재(남은) 인원 모두가 원하는 샌드위치를 먹지 못할 경우 return으로 반복문을 종료했다. 현재 사람이 원하는 샌드위치를 가졌을 때는 pop() 메서드를 사용했기 때문에 리스트(스택)에서 자동으로 없어진다.

class Solution:
    def countStudents(self, students: List[int], sandwiches: List[int]) -> int:
        while True:
            if len(students) == 0:
                return 0
            
            stu = students.pop(0)
            sand = sandwiches.pop(0)
            count = 0 # 못 먹는 사람 수

            for i in students:
                if i not in sandwiches:
                    count += 1
                
        if count == len(students):  # 현재 인원 전부 다 못 먹으면
                return count

            if stu != sand:
                students.append(stu)
                sandwiches.insert(0, sand)

이 코드의 문제점은 다음과 같고, 해결한 답이 글 위쪽의 My Solution 부분이다.

 

현재 남은 학생들이 남은 샌드위치 중 하나도 먹을 수 없으면, 반복문을 종료하려고 했다.

→ 그런데 검사를 위해 while문 안에서 for문을 중첩하여, 불필요하게 반복마다 전체를 다 검사하려고 했다.

→ 해답 코드에서는 학생 수를 세는 count 변수와 현재 남은 학생 수를 비교하며 종료 조건을 구현했다. 

 

• 반복문 사용 시, 어떤 내용이 반복적으로 수행되어야 하는지를 최대한 간단하게 생각하자.