[2024] day 166. leetcode 2037. Minimum Number of Moves to Seat Everyone

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 6월 13일 (목)
Leetcode daily problem

2037. Minimum Number of Moves to Seat Everyone

https://leetcode.com/problems/minimum-number-of-moves-to-seat-everyone/?envType=daily-question&envId=2024-06-13

Problem

한 방에 n개의 좌석과 n명의 학생이 있다.
길이가 n인 seats 좌석이 주어질 때 여기서 seats[i]은 i번째 좌석의 위치이다. 길이가 n인 students 배열에서 students[j]는 j번째 학생의 위치이다.

다음 동작은 횟수 제한 없이 수행할 수 있는데,

• i번째 학생의 위치를 1만큼 늘리거나 줄일 수 있다.
  (즉, i번째 학생을 위치 x에서 x + 1 또는 x - 1로 이동)

• 두 명의 학생이 같은 자리에 앉지 않도록 각 학생을 한 자리로 이동하는 데 필요한 최소 이동 횟수를 반환한다.

처음에는 같은 위치에 여러 좌석이나 학생이 있을 수 있다.

Solution

sort

최소 이동 횟수를 구하기 위해서는 주어진 좌석과 가장 가까운 학생이 매칭되는 것이 좋으므로, seats와 students를 오름차순으로 정렬한 후에, 정렬된 각 좌석과 학생들의 차이에 대한 값들을 더하면서 업데이트하고 마지막 합을 반환한다.

Code

class Solution:
    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:
        ans = 0
        for seat, student in zip(sorted(seats), sorted(students)):
            ans += abs(student-seat)
            
        return ans

Complexicity

시간 복잡도

좌석과 학생 배열을 정렬하는데 O(nlogn)이 소요되고,
정렬한 학생과 좌석을 한번씩 탐새하는데 O(n)이 소요된다.
총 시간 복잡도는 O(n)이다.

공간 복잡도

배열을 정렬하면서 추가공간 O(n)을 필요로한다.
총 공간 복잡도는 O(n) 이다.