99클럽 코테 스터디 24일차 TIL + 탐욕법 Greedy, [leetcode] Minimum Number of Moves to Seat Everyone

✨ 문제 

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.

 

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

 

 

 

✨ 개념

Greedy 탐욕법

- 탐욕 알고리즘은 문제 상황에서 그 상황에서 가장 최선의 선택을 하는 알고리즘이다.

- 주어진 상황에서 가장 선택을 하기 때문에 최종값에 대한 최선의 값임을 보장하지는 못한다.

 

 

 

✨ 최종코드

class Solution {
    public int minMovesToSeat(int[] seats, int[] students) {
        int result = 0 ;
        
        Arrays.sort(seats);
        Arrays.sort(students);
        
        for (int i = 0; i < students.length; i++)
            result += Math.abs(seats[i] - students[i]);
        
        return result;        
    }
}

 

문제는 좌석 번호가 적힌 배열 seats와 학생이 위치한 번호 배열 students가 주어진다. seats와 students의 길이는 같다. 이때 모든 학생을 좌석에 앉히는데 가장 최소한으로 움직이도록 했을 때의 총 움직인 횟수를 반환해야 한다.

일단 총 움직인 횟수를 저장할 변수 result를 선언한다. 그리고 주어진 배열 seats와 students를 모두 정렬한 뒤 for문을 students 배열의 길이만큼 돌린다. Math.abs()를 사용해 seats[i]와 students[i]의 절댓값을 구해 result에 더한다.

for문이 종료되면 result를 반환한다.