99클럽 코테 스터디 34일차 TIL (비기너)

<문제>

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.

You are given two integer arrays students and sandwiches where sandwiches[i] is the type of the i​​​​​​th sandwich in the stack (i = 0 is the top of the stack) and students[j] is the preference of the j​​​​​​th student in the initial queue (j = 0 is the front of the queue). Return the number of students that are unable to eat.

Example 1:

Input: students = [1,1,0,0], sandwiches = [0,1,0,1]
Output: 0 
Explanation:
- Front student leaves the top sandwich and returns to the end of the line making students = [1,0,0,1].
- Front student leaves the top sandwich and returns to the end of the line making students = [0,0,1,1].
- Front student takes the top sandwich and leaves the line making students = [0,1,1] and sandwiches = [1,0,1].
- Front student leaves the top sandwich and returns to the end of the line making students = [1,1,0].
- Front student takes the top sandwich and leaves the line making students = [1,0] and sandwiches = [0,1].
- Front student leaves the top sandwich and returns to the end of the line making students = [0,1].
- Front student takes the top sandwich and leaves the line making students = [1] and sandwiches = [1].
- Front student takes the top sandwich and leaves the line making students = [] and sandwiches = [].
Hence all students are able to eat.

Example 2:

Input: students = [1,1,1,0,0,1], sandwiches = [1,0,0,0,1,1]
Output: 3

Constraints:

• 1 <= students.length, sandwiches.length <= 100

• students.length == sandwiches.length

• sandwiches[i] is 0 or 1.

• students[i] is 0 or 1.

<문제해설>

두 개의 배열 (학생, 샌드위치)이 주어진다. 두 배열은 0, 1로만 이루어져있다.

두 배열의 첫 번째 원소가 같으면 각각 첫 번째 원소를 삭제한다.

첫 번째 원소가 다르면 학생 배열의 첫 번째 원소를 맨 뒤로 보낸다. 샌드위치 배열의 원소는 그대로 둔다. (원하는 샌드위치가 아닌 경우 샌드위치는 그대로 있고 첫 번째 학생이 맨 뒤로 간다)

첫 번째 샌드위치를 원하는 학생이 아무도 없을 때 까지 반복한다.

<풀이>

class Solution {
    public int countStudents(int[] students, int[] sandwiches) {
        //한 가지 숫자만 남으면 끝! ...가 아니었네!ㅠ
        ArrayDeque<Integer> stQueue = returnDeque(students);
        ArrayDeque<Integer> sdQueue = returnDeque(sandwiches);

        int answer = 0;

        while(true){
            //            if(stQueue.size() == 0){
            if(stQueue.isEmpty()){
                break;
            }

            //한 가지 숫자만 남았는지 판단하기 (X) ==> 문제 잘못 이해함!
//            if(hasOneNumbers(stQueue) + hasOneNumbers(sdQueue) == 1){
//                answer = sdQueue.size();
//                break;
//            }

            //top 샌드위치와 일치하는 요소가 하나도 없으면 중단
            if(!wantTopSandwich(stQueue, sdQueue.getFirst())){
                answer = sdQueue.size();
                break;
            }

            int student = stQueue.poll();
            int sandwich = sdQueue.poll();

            if(student != sandwich){
                stQueue.offer(student);//맨뒤에넣는다
                sdQueue.push(sandwich);//맨앞에넣는다(원복)
            }

        }

        return answer;
        
    }
    
   public static boolean wantTopSandwich(ArrayDeque<Integer> param, int topSandwich){
        ArrayDeque<Integer> deque = param.clone();

        for (Integer i : deque) {
            if(i == topSandwich) { //하나라도 일치하면 true 반환
                return true;
            }
        }

        return false; //일치하는 요소가 하나도 없으면 false 반환
    }

    public static ArrayDeque<Integer> returnDeque(int[] arr){
        ArrayDeque<Integer> deque = new ArrayDeque();
        for(int i:arr){
            deque.offer(i);
        }
        return deque;
    }
    
}

2시간 넘게 걸렸다.. ^_ㅠ

<접근방식>

스택, 큐 문제라는 것을 알고 있었기 때문에 ArrayDeque를 사용했다.

<다른코드참고>

너무 간단한데.. 이해를 못했다. 지금은 머리가 아프니까 나중에 이해해봐야겠다!

class Solution {
    public int countStudents(int[] students, int[] sandwiches) {
        int[] counts = new int[2];
        for (int student : students) counts[student]++;
        
        int remaining = sandwiches.length;
        for (int sandwich : sandwiches) {
            if (counts[sandwich] == 0) break;
            if (remaining-- == 0) break;
            counts[sandwich]--;
        }
        
        return remaining;
    }
}

https://leetcode.com/problems/number-of-students-unable-to-eat-lunch/discuss/4990164/Beats-98.93-oror-Extra-Easy-Solution-with-Explanation.

<마무리하며>

1. 문제를 꼼꼼히 읽자.. 잘못 접근해서 1시간 반 동안 헤맸다..

   This continues until none of the queue students want to take the top sandwich and are thus unable to eat. => 어떻게 풀면 되는지 문제에 대놓고 나와 있었다.

   첫 번째 샌드위치를 원하는 학생이 아무도 없다는 것만 검증하면 되는 거였는데, 모든 샌드위치를 아무도 원하지 않는지 검증하는 줄 알고 엄청 어렵게 생각했다..!

2. Stack, Queue 공부하자. 아는데서 자신감이 나온다!!

   모르는 용어 나오니까 괜히 어렵다고 겁먹고 시야가 좁아져서 문제도 잘못 이해했다.

3. 다음 기수에서 계속 비기너를 할지, 미들러를 할지 고민중이다. 앞으로 일주일 동안 남은 문제를 풀어보고 판단해봐야겠다.

4. 어제 바빠서 문제를 못 풀었다. 스벅 아아가 날아갔다 ㅠ

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL