[LeetCode | Java | Greedy 문제 풀이] 2037. Minimum Number of Moves to Seat Everyone - Solution with Arrays.sort()

99 Club 2기 | Java | Beginner

🪑 2037. Minimum Number of Moves to Seat Everyone

🏷 관련 주제 : Array Greedy Sorting

Easy

There are n seats and n students in a room. You are given an array seats of length n, where seats[i] is the position of the $i^{th}$ seat. You are also given the array students of length n, where students[j] is the position of the $j^{th}$ student.


You may perform the following move any number of times:

 

• Increase or decrease the position of the $i^{th}$ student by 1 (i.e., moving the $i^{th}$ student from position x to x + 1 or x - 1)

 

Return the minimum number of moves required to move each student to a seat such that no two students are in the same seat.

 

Note that there may be multiple seats or students in the same position at the beginning.

 

Example 1:

Input: seats = [3,1,5], students = [2,7,4]
Output: 4
Explanation: The students are moved as follows:

• The first student is moved from from position 2 to position 1 using 1 move.
• The second student is moved from from position 7 to position 5 using 2 moves.
• The third student is moved from from position 4 to position 3 using 1 move.
  In total, 1 + 2 + 1 = 4 moves were used.

Example 2:

Input: seats = [4,1,5,9], students = [1,3,2,6]
Output: 7
Explanation: The students are moved as follows:

• The first student is not moved.
• The second student is moved from from position 3 to position 4 using 1 move.
• The third student is moved from from position 2 to position 5 using 3 moves.
• The fourth student is moved from from position 6 to position 9 using 3 moves.
  In total, 0 + 1 + 3 + 3 = 7 moves were used.

Example 3:

Input: seats = [2,2,6,6], students = [1,3,2,6]
Output: 4
Explanation: Note that there are two seats at position 2 and two seats at position 6.
The students are moved as follows:

• The first student is moved from from position 1 to position 2 using 1 move.
• The second student is moved from from position 3 to position 6 using 3 moves.
• The third student is not moved.
• The fourth student is not moved.
  In total, 1 + 3 + 0 + 0 = 4 moves were used.

Constraints:

• n == seats.length == students.length
• 1 <= n <= 100
• 1 <= seats[i], students[j] <= 100

 

Accepted    127.3K  |  Submissions    147.7K  |  Acceptance Rate    86.2%

---

✔ Solution with Arrays.sort()

import java.util.Arrays;

class Solution {
    public int minMovesToSeat(int[] seats, int[] students) {
        int answer = 0;
        Arrays.sort(seats);
        Arrays.sort(students);

        for (int i = 0; i < seats.length; i++) {
            int move = seats[i] - students[i];

            if (move < 0) {
                answer -= move;
            } else if (move > 0) {
                answer += move;
            }
        }

        return answer;
    }
}

채점 결과

 

💥 오늘 만난 문제 & 나의 시도 💦 & 해결 방법 👍

📌 오늘 만난 문제 : 매개변수로 의자가 있는 위치 배열 seats와 학생이 있는 위치 배열 students가 주어질 때,
각각의 학생 의자에 앉기 위한 최소한의 움직임을 반환하라.
학색은 한번에 1씩만 움직일 수 있으며 서로 다른 학생은 서로 다른 의자에 앉아야 한다.

---

각각의 학생의 최소한의 움직임으로 자리에 앉기 위해
각 학생에 대하여 가장 근처에 있는 의자를 찾아야 한다.

1. 학생들이 움직인 총 횟수를 담을 변수 answer 초기화하기

  int answer = 0;

 

2. seats와 numbers를 정렬하기

  Arrays.sort(seats);
  Arrays.sort(students);

 

3. 0번 인덱스부터 차례대로 seats와 numbers의 원소를 꺼내 두 원소 간의 거리를 answer에 더해주자.

• 두 원소간의 차를 int move에 할당하자.
• 두 원소 간의 거리는 항상 양수이므로
  • 두 원소 간의 차가 음수이면, answer에 두 수의 차를 빼자.
  • 두 원소 간의 차가 양수이면, answer에 두 수의 차를 합하자.

  for (int i = 0; i < seats.length; i++) {
    int move = seats[i] - students[i];
  
    if (move < 0) {
        answer -= move;
    } else if (move > 0) {
        answer += move;
    }
  }

4. answer에 할당된 값을 반환하자.

return answer;

 

💬 무엇을 새롭게 알았는지

Greedy 문제인데 제대로 푼 것인지 잘 모르겠지만
문제에서 관련 주제라고 한 Array와 Sorting은 이용한 것 같다.
Greedy에 대한 공부가 더 필요해 보인다.

---

🆙 Next Level

• 미들러: 🥇 순위
• 챌린저: 🔀 1971. Find if Path Exists in Graph