99클럽(2기) - 코테스터디 16일차 TIL # Graph

LeetCode - 2037. Minimum Number of Moves to Seat Everyone

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 ith seat. You are also given the array students of length n, where students[j] is the position of the jth student.

You may perform the following move any number of times:

• Increase or decrease the position of the ith student by 1 (i.e., moving the ith 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.

---

 

1. 첫 번째 풀이

1) seats와 students를 오름차순으로 정렬

 학생과 가장 가까운 좌석은 자신과 비슷한 순번을 가진 좌석이기 때문에 seats와 students를 오름차순으로 정렬했다. 

 

2) seats와 students간 서로 대응되는 요소의 차이를 구하고 그 합을 구해서 반환

 학생이 자신과 가장 가까운 좌석으로 이동해야하는 횟수는 동일한 인덱스를 가진 seats의 요소와 students의 요소의 차이이다. abs함수는 인풋의 절대값을 반환하므로 seats의 값에서 students의 값을 뺀 값에 abs함수를 적용해 최소 움직임 횟수를 구한다. 반환해야 하는 값은 그 최소의 움직임들의 합이기 때문에 sum으로 합을 구해서 반환하면 끝! 

from typing import List
class Solution:
    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:
        # seats와 students를 오름차순으로 정렬
        seats.sort()
        students.sort()
        
        # seats와 students 사이에 대응되는 값들의 차이들의 합을 반환
        return sum([abs(seats[i] - students[i]) for i in range(len(seats))])

 

 

2. 두 번째 풀이

 챗지피티에게 풀이를 부탁하니 그리디로 풀어줬다. 

 

1) 사용 가능한 좌석 초기화
 seats와 students의 최대 위치 인덱스를 계산해 max_position에 할당하고, available_seats에 max_position 수만큼의 0으로 구성된 배열을 할당한다. 그 후 모든 요소가 0으로 초기화되어있는 available_seats에 seats에 존재하는 좌석과 동일한 위치의 값을 1로 변경한다. 

2) 각 학생을 좌석과 연결
 students의 학생별로 현재 위치에서 가장 가까우면서 사용 가능한 좌석을 확인한다. 현재 move_count 내에서 사용 가능한 좌석을 발견하면 available_seats 배열에서 해당 위치를 사용 불가 상태(0)로 업데이트하고 total_moves를 move_count만큼 증가시킨 후 루프를 빠져나온다. 사용 가능한 좌석이 없으면 move_count를 증가시키고 다음으로 가장 가까운 위치를 확인한다. 

from typing import List

class Solution:
    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:
        max_position = max(max(seats), max(students)) + 1
        available_seats = [0] * max_position
        
        # Mark available seats
        for seat in seats:
            available_seats[seat] += 1
        
        total_moves = 0
        
        # Match each student to the nearest available seat
        for student in students:
            move_count = 0
            while True:
                if student - move_count >= 0 and available_seats[student - move_count] > 0:
                    available_seats[student - move_count] -= 1
                    total_moves += move_count
                    break
                if student + move_count < max_position and available_seats[student + move_count] > 0:
                    available_seats[student + move_count] -= 1
                    total_moves += move_count
                    break
                move_count += 1
        
        return total_moves

 

 

3. 느낀점

 정렬 기반의 풀이가 더 효율적지만 탐욕적 접근 방식을 통해 학생과 좌석을 직접 연결해 따져보는 방법에 대해서도 학습해보았다.