99클럽 코테 스터디 15일차 2037. Minimum Number of Moves to Seat Everyone / 최소 이동 거리 보장의 증명

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

 

모든 사람을 앉히는 데 필요한 최소 이동 횟수

 

여러분은 n개의 좌석과 n명의 사람을 가지고 있습니다. 각각의 사람들은 특정 위치에 서 있으며, 여러분은 이 사람들을 좌석으로 이동시키고자 합니다. 사람들의 초기 위치는 seats라는 배열로 주어지고, 사람들의 현재 위치는 people이라는 배열로 주어집니다.

여러분은 다음과 같은 규칙에 따라 사람들을 이동시킬 수 있습니다:

• 각 이동은 사람을 인접한 위치로 한 칸 이동시킵니다. 예를 들어, 사람이 위치 x에 있다면, 그는 x + 1 또는 x - 1로 이동할 수 있습니다.

여러분의 목표는 모든 사람을 하나의 좌석에 앉히는 데 필요한 최소 이동 횟수를 구하는 것입니다.

 

 

 

 

이번 문제는 바로 풀이를 기술하지 않고, 처음에 잘못된 방향성(?)을 잡았기에, 수학적인 사실과 함께 오답을 통한 오답 노트를 먼저 작성하겠다.

 

[처음 쓴 오답]

1.

class Solution:
    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:
        total_count=0
        for i in range(len(seats)-1):
            for j in range(len(students)-1):
                moving_count=[]
                if seats[i]<=students[j]:
                    moving_count.append(students[j]-seats[i])
                else:
                    moving_count.append(seats[i]-students[j])
            total_count += min(moving_count)
        return total_count

 

이 코드가 틀린 이유는 다음의 3가지가 있다.

 

문제점 (GPT 자문)

1. 중첩 반복문의 오해: 현재 코드에서는 seats와 students 배열에 대해 두 개의 중첩된 반복문을 사용하고 있는데, 이 방법은 잘못된 방식입니다. 이는 각각의 seats[i]에 대해 모든 students[j]와 비교한 다음, 그 중 가장 적은 이동 거리만을 total_count에 추가하고 있습니다. 이는 모든 사람과 좌석의 쌍을 개별적으로 비교하고 최적의 쌍을 찾지 않기 때문에, 문제의 의도에 맞지 않습니다.
2. 이동 거리의 누락: moving_count 리스트를 중첩된 반복문 안에서 생성하고 있는데, 이는 결국 모든 좌석과 학생의 조합에 대해 이동 거리를 계산하지만, 마지막 min(moving_count)만을 total_count에 추가합니다. 이는 이동 거리의 누락을 발생시킵니다.
3. 정렬의 필요성: 이 문제를 해결하는 올바른 방법은 seats와 students를 모두 정렬한 후에, 각 학생을 가장 가까운 좌석으로 이동시키는 것입니다. 이 방법은 이동 거리를 최소화합니다.

 

이를 정리하자면, 크게 두가지 오류를 범하였다.

 

첫번째, min moving count 만 total에 추가하게 되면 이동거리에 누락이 생긴다.

두번째, 거리 최솟값을 구하기 위해선, 정렬을 해야한다

 

 

거리 최솟값을 구하기 위해서 정렬을 해야 하는 이유는, 다음과 같이 수학적으로 증명할 수 있다.

 

최소 이동 거리 보장의 증명

1. 정렬된 리스트에서 최소 이동 거리의 보장: 정렬된 리스트 seats와 students가 있다고 가정합시다. 두 리스트는 각각 오름차순으로 정렬되어 있습니다.
   • 예를 들어, seats = [s1, s2, s3, ..., sn]와 students = [p1, p2, p3, ..., pn]가 있습니다.
   • 각 i에 대해 |si - pi|는 si와 pi 사이의 거리입니다.
   • 우리는 이 거리를 최소화하려고 합니다.
2. 역설적인 상황 가정: 만약 정렬된 상태에서 매칭된 쌍이 아닌 다른 방법이 더 작은 이동 거리를 제공한다고 가정해봅시다. 즉, 최소 거리를 얻기 위해 seats[i]와 students[i]가 아닌 seats[i]와 다른 students[j]를 매칭한다고 생각해 봅시다.
3. 대칭성과 최적화: 정렬된 상태에서 seats[i]와 students[i]의 거리가 아닌 seats[i]와 students[j]를 비교하면:
   • |seats[i] - students[j]|는 일반적으로 |seats[i] - students[i]|보다 크거나 같습니다.
   • 이는 정렬된 리스트의 특성 때문입니다. 즉, 인접한 요소들이 더 가까이 있기 때문에 발생합니다.
   • 따라서, 두 리스트를 정렬하여 같은 인덱스의 요소를 매칭하는 것은 항상 다른 매칭 방법보다 작은 이동 거리를 제공합니다.

 

따라서, 정렬을 해야 각 요소간의 최소 거리를 구할 수 있는 것 이다.

 

이 사실에 유의하여 다음과 같이 코드를 작성하였다.

 

class Solution:
    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:
        seats.sort()
        students.sort()
        total_count=0
        for i in range(len(seats)):
            if seats[i]<=students[i]:
                total_count += students[i]-seats[i]
            else:
                total_count += seats[i]-students[i]
        return total_count

 

드디어 통과할 수 있었다.

비교를 하지 않고 abs 함수를 이용해 절댓값을 구하면, 좀 더 간단하게 코드를 작성할 수 있다.

 

class Solution:
    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:
    	# 좌석과 학생 위치 정렬
        seats.sort()
        students.sort()
        total_count=0
        	
        # 정렬된 좌석과 학생의 위치를 순서대로 비교하여 이동거리 계산
        for i in range(len(seats)):
            total_count += abs(seats[i] - students[i])
        return total_count

 

정답을 찾아감에 있어서는, 수학적인 사실에 대해서도 어느정도 알아둘 필요가 있다.