leetcode 849) Maximize Distance to Closest Person

LV. Medium 🧐

https://leetcode.com/problems/maximize-distance-to-closest-person/

Maximize Distance to Closest Person - LeetCode

 

문제

You are given an array representing a row of seats where seats[i] = 1 represents a person sitting in the ith seat, and seats[i] = 0 represents that the ith seat is empty (0-indexed).

There is at least one empty seat, and at least one person sitting.

Alex wants to sit in the seat such that the distance between him and the closest person to him is maximized. 

Return that maximum distance to the closest person.

 

Example 1:

Input: seats = [1,0,0,0,1,0,1]
Output: 2
Explanation: 
If Alex sits in the second open seat (i.e. seats[2]), then the closest person has distance 2.
If Alex sits in any other open seat, the closest person has distance 1.
Thus, the maximum distance to the closest person is 2.

Example 2:

Input: seats = [1,0,0,0]
Output: 3
Explanation: 
If Alex sits in the last seat (i.e. seats[3]), the closest person is 3 seats away.
This is the maximum distance possible, so the answer is 3.

Example 3:

Input: seats = [0,1]
Output: 1

 

Constraints:

• 2 <= seats.length <= 2 * 10^4
• seats[i] is 0 or 1.
• At least one seat is empty.
• At least one seat is occupied.

 

문제 해결법

연속으로 비어있는 자리의 max를 찾아준다.

비어있는 자리 중간에 알렉스가 앉게 되므로, max / 2 한 값을 리턴해주면 된다.

 

예외적으로 0번째 인덱스와 마지막 인덱스 따로 계산해줘야 된다.

0번째 인덱스와 마지막 인덱스가 0인 경우에는 연속적인 자리 중간에 알렉스가 앉는 게 아니라 해당 자리 (0인덱스, 마지막 인덱스)에 앉는다.

0번째 인덱스와 마지막 인덱스의 자리가 비어있으면, 연속적으로 비어있는 자리의 두 배를 해 맥스 계산을 해준다.

 

해결 코드

class Solution {
public:
	int maxDistToClosest(vector<int>& seats) {
		int num = 0;
		int num_max = 0;
		bool flag = !seats[0];

		for (int i = 0; i < seats.size(); ++i) {
			if (seats[i] == 0)
				num++;
			else {
				if (flag) {
					num_max = max(num * 2, num_max);
					flag = false;
				}
				else if (num > 0)
					num_max = max(num_max, num + 1);
				num = 0;
			}
		}
		if (num != 0)
			num_max = max(num * 2, num_max);
		cout << num_max << endl;
		return num_max / 2;
	}
};