10-3. Flags
A non-empty array A consisting of N integers is given.
A peak is an array element which is larger than its neighbours. More precisely, it is an index P such that 0 < P < N − 1 and A[P − 1] < A[P] > A[P + 1].
For example, the following array A:
A[0] = 1
A[1] = 5
A[2] = 3
A[3] = 4
A[4] = 3
A[5] = 4
A[6] = 1
A[7] = 2
A[8] = 3
A[9] = 4
A[10] = 6
A[11] = 2has exactly four peaks: elements 1, 3, 5 and 10.
You are going on a trip to a range of mountains whose relative heights are represented by array A, as shown in a figure below. You have to choose how many flags you should take with you. The goal is to set the maximum number of flags on the peaks, according to certain rules.
Flags can only be set on peaks. What's more, if you take K flags, then the distance between any two flags should be greater than or equal to K. The distance between indices P and Q is the absolute value |P − Q|.
For example, given the mountain range represented by array A, above, with N = 12, if you take:
two flags, you can set them on peaks 1 and 5;
three flags, you can set them on peaks 1, 5 and 10;
four flags, you can set only three flags, on peaks 1, 5 and 10.
You can therefore set a maximum of three flags in this case.
Write a function:
class Solution { public int solution(int[] A); }
that, given a non-empty array A of N integers, returns the maximum number of flags that can be set on the peaks of the array.
For example, the following array A:
A[0] = 1
A[1] = 5
A[2] = 3
A[3] = 4
A[4] = 3
A[5] = 4
A[6] = 1
A[7] = 2
A[8] = 3
A[9] = 4
A[10] = 6
A[11] = 2the function should return 3, as explained above.
Write an efficient algorithm for the following assumptions:
N is an integer within the range [1..400,000];
each element of array A is an integer within the range [0..1,000,000,000].
비어 있지 않은 정수 배열 A가 주어집니다. 이 배열은 N개의 정수로 구성되어 있습니다.
피크(peak)는 이웃한 요소들보다 큰 배열 요소입니다. 더 정확히 말하면, 피크는 0 < P < N − 1이고 A[P − 1] < A[P] > A[P + 1]인 인덱스 P입니다.
예를 들어, 다음과 같은 배열 A가 있습니다:
A[0] = 1
A[1] = 5
A[2] = 3
A[3] = 4
A[4] = 3
A[5] = 4
A[6] = 1
A[7] = 2
A[8] = 3
A[9] = 4
A[10] = 6
A[11] = 2이 배열에는 정확히 네 개의 피크가 있습니다: 요소 1, 3, 5, 10.
당신은 산맥을 여행할 예정이며, 이 산맥의 상대적인 높이는 배열 A로 나타냅니다. 목표는 피크에 최대한 많은 깃발을 세우는 것입니다. 깃발을 세우는 규칙은 다음과 같습니다:
깃발은 피크에만 세울 수 있습니다. 또한, K개의 깃발을 세우려면 두 깃발 사이의 거리가 K 이상이어야 합니다. 인덱스 P와 Q 사이의 거리는 절대값 |P − Q|입니다.
예를 들어, 주어진 배열 A에서 N = 12일 때:
두 개의 깃발을 세우려면 피크 1과 5에 세울 수 있습니다. 세 개의 깃발을 세우려면 피크 1, 5, 10에 세울 수 있습니다. 네 개의 깃발을 세우려면 피크 1, 5, 10에 세울 수 있습니다. 따라서 이 경우 최대 세 개의 깃발을 세울 수 있습니다.
다음 함수를 작성하세요:
class Solution {
public int solution(int[] A);
}이 함수는 비어 있지 않은 정수 배열 A가 주어졌을 때, 배열의 피크에 세울 수 있는 최대 깃발 수를 반환해야 합니다.
예를 들어, 다음과 같은 배열 A가 주어졌을 때:
A[0] = 1
A[1] = 5
A[2] = 3
A[3] = 4
A[4] = 3
A[5] = 4
A[6] = 1
A[7] = 2
A[8] = 3
A[9] = 4
A[10] = 6
A[11] = 2함수는 위에서 설명한 대로 3을 반환해야 합니다.
다음 가정을 위한 효율적인 알고리즘을 작성하세요:
N은 [1…400,000] 범위 내의 정수입니다. 배열 A의 각 요소는 [0…1,000,000,000] 범위 내의 정수입니다.
문제풀이
import java.util.*;
class Solution {
public int solution(int[] A) {
int N = A.length;
if (N < 3) return 0;
List<Integer> peaks = new ArrayList<>();
for (int i = 1; i < N - 1; i++) {
if (A[i] > A[i-1] && A[i] > A[i+1]) {
peaks.add(i);
}
}
if (peaks.size() == 0) return 0;
int left = 1;
int right = peaks.size();
int maxFlags = 0;
while (left <= right) {
int mid = (left + right) / 2;
if (canPlaceFlags(peaks, mid)) {
maxFlags = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return maxFlags;
}
private boolean canPlaceFlags(List<Integer> peaks, int k) {
int flags = 1;
int lastFlag = peaks.get(0);
for (int i = 1; i < peaks.size(); i++) {
if (peaks.get(i) - lastFlag >= k) {
flags++;
lastFlag = peaks.get(i);
if (flags == k) return true;
}
}
return false;
}
}제출결과
문제풀어보기 -> https://app.codility.com/programmers/lessons/10-prime_and_composite_numbers/flags/
