[leetcode #849] Maximize Distance to Closest Person
Problem
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⁴ ・ seats[i] is 0 or 1. ・ At least one seat is empty. ・ At least one seat is occupied.
Idea
Alex가 다른 승객들로부터 가장 멀리 떨어진 자리에 앉았을 때 거리를 구하는 문제다.
승객들이 앉은 상태인 seats를 왼쪽과 오른쪽으로 각각 탐색하면서 떨어진 거리를 먼저 구한다. 이 때 시작점에 승객이 없을 경우 거리를 주어진 조건의 최대값인 20,000으로 정한다.
왼쪽과 오른쪽 거리를 구한 뒤 두 값을 비교하여 최소값을 거리로 정한다. 이 때 정한 거리들 중 최대가 되는 값이 Alex가 가장 멀리 떨어진 자리에 앉았을 때의 거리가 된다.
Solution
class Solution {
public int maxDistToClosest(int[] seats) {
int[] left = new int[seats.length];
int[] right = new int[seats.length];
int distance = 20_000;
for (int i=0; i < seats.length; i++) {
if (seats[i] == 1) {
distance = 0;
} else {
distance++;
}
left[i] = distance;
}
distance = 20_000;
for (int i=seats.length-1; i >= 0; i--) {
if (seats[i] == 1) {
distance = 0;
} else {
distance++;
}
right[i] = distance;
}
int res = 0;
for (int i=0; i < seats.length; i++) {
distance = Math.min(left[i], right[i]);
res = Math.max(res, distance);
}
return res;
}
}
Reference
https://leetcode.com/problems/maximize-distance-to-closest-person/
Author And Source
이 문제에 관하여([leetcode #849] Maximize Distance to Closest Person), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@timevoyage/leetcode-849-Maximize-Distance-to-Closest-Person저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)