[LeetCode] 915. Partition Array into Disjoint Intervals

https://leetcode.com/problems/partition-array-into-disjoint-intervals/

Partition Array into Disjoint Intervals.

 

숫자로 된 배열이 주어졌을때, 배열을 두 배열로 나누는 문제이다.

이 때, 배열은 왼쪽과 오른쪽으로 나뉘게 되는데 

왼쪽의 모든 배열은 오른쪽의 어떤 배열보다도 작거나 같아야한다.

또한 배열은 원래 순서 그대로 이어져 있어야 한다.

 

즉 Example1 에서, [5, 0, 3, 8, 6] 을 보면

배열을 나누는 방법은

 

[5], [0, 3, 8, 6]

[5, 0], [3, 8, 6]

[5, 0, 3], [8, 6]

[5, 0, 3, 8], [6]

 

이렇게 네 가지가 된다. 각각을 보면

 

[5], [0, 3, 8, 6] => 오른쪽 배열이 왼쪽배열보다 무조건 크거나 같아야 하는데, 오른쪽의 0,3은 왼쪽의 5보다 작으므로 안된다.

[5, 0], [3, 8, 6] => 역시나 3이 5보다 작으므로 안 된다.

[5, 0, 3], [8, 6] => 8, 6은 5, 0, 3 어떤 수보다도 크거나 같으므로 괜찮다.

[5, 0, 3, 8], [6] => 6이 8보다 작으므로 안 된다.

 

Example1 의 경우에는 딱 한 가지의 경우만 존재한다.

하지만 여러개의 경우가 존재할 수도 있는데, 왼쪽 배열의 개수가 최소일 때 그 개수를 출력해야 한다.

 

문제의 조건을 다시 살펴보자.

왼쪽 배열의 모든 수가 오른쪽 배열의 어떠한 수보다도 작거나 같아야 한다.

이를 달리 말하면, 왼쪽 배열의 최대값이 오른쪽 배열의 최소값보다 작거나 같으면 된다.

 

모든 배열을 검사하는 과정이 수를 하나씩만 비교해 보면 되는 문제로 바뀌었다.

 

그렇다면 문제는 최대값과 최소값은 어떻게 찾아낼까??

 

왼쪽 배열과 오른쪽 배열은 연속되어 있다. 또한 이들은 어떤 경계를 갖고 만나게 된다.

우리는 배열을 딱 한번씩만 훑으며 최소값과 최대값을 저장할 것이다.

 

우리는 왼쪽 배열에서 다른 값은 필요가 없고 최대값만 필요하다.

따라서 배열을 훑으면서 최대값만 저장해주자.

 

편의상 초기에 배열의 모든 값을 0번 인덱스의 값으로 초기화 시켜주고 시작하자.

그 후, 해당 인덱스의 최대값은 그 직전 인덱스의 최대값과 현재 인덱스의 값 중 최대값으로 저장해주면 된다.

Arr	5	0	3	8	6
Max	5	5	5	8	8

int max_arr[1000001];
for (int i=0; i<nums.size(); i++) max_arr[i]=nums[0];
for (int i=1; i<nums.size(); i++) max_arr[i] = max(max_arr[i-1], nums[i]);

 

반대로 오른쪽 배열에서는 최소값만 필요하다.

역시나 배열을 훑으며 최소값만 저장해주자.

주의할 점은, 오른쪽 배열은 시작과 이어지지 않고 끝과 이어져 있으므로 끝에서 부터 거꾸로 훑어줘야 한다.

Arr	5	0	3	8	6
min	0	0	3	6	6

int min_arr[1000001];
for (int i=0; i<nums.size(); i++) min_arr[i]=nums[nums.size()-1];
for (int i=1; i<nums.size(); i++) min_arr[nums.size()-1-i] = min(min_arr[nums.size()-i],nums[nums.size()-i-1]);

 

마지막으로 최대값과 최소값 배열을 비교해보자.

왼쪽 배열의 최대값이 오른쪽 배열의 최소값보다 작거나 같아야 하므로,

i번째 최대값 배열과 i+1번째 최소값 배열을 비교해주자.

Max	5	5	5	8	8
min	0	0	3	6	6

왼쪽배열 길이가 최소일때를 찾아야 하므로,

배열의 길이대로 차례대로 훑으면서 해당하는 인덱스가 있을 경우 바로 1을 더해 리턴해주면 된다.

(1을 더하는 이유는 길이를 구해야 하므로!)

 

위의 예시에서는 Max[2] = 5 <= 6 = min[2+1] = min[3] 이 최초로 성립하므로 답은 3이 된다.

for (int i=0; i<nums.size()-1; i++) if (max_arr[i]<=min_arr[i+1]) {
	ret=i+1;
	break;
}

 

전체 코드는 아래와 같다.

 

class Solution {
public:
    int partitionDisjoint(vector<int>& nums) {
        int ret = 0;
        int max_arr[1000001], min_arr[1000001];
        for (int i=0; i<nums.size(); i++) {max_arr[i]=nums[0];min_arr[i]=nums[nums.size()-1];}
        for (int i=1; i<nums.size(); i++) {
            max_arr[i] = max(max_arr[i-1], nums[i]);
            min_arr[nums.size()-1-i] = min(min_arr[nums.size()-i],nums[nums.size()-i-1]);
        }
        for (int i=0; i<nums.size()-1; i++) if (max_arr[i]<=min_arr[i+1]) {ret=i+1;break;}
        return ret;
    }
};