Codility Lesson 10 - Flags(JAVA)

https://app.codility.com/programmers/lessons/10-prime_and_composite_numbers/flags/

Flags coding task - Learn to Code - Codility

 

문제

- 배열 A는 N개의 정수들로 이루어져 있다.

- peak란 주변의 값보다 큰 수를 의미한다. inedx P일 때, 0 < P < N − 1 and A[P − 1] < A[P] > A[P + 1]인 값을 의미

- 예시 : 

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

이 때 peaks는 1, 3, 5, 10일 때이다.

- 깃발을 꽂기 위해서는 peaks에만 꽂을 수 있고, K 개의 깃발을 꽂는다고 할 때, 어떠한 2개의 깃발 사이의 거리도 K와 같거나 그 이상이여야 합니다. 거리는 P, Q의 차의 절대값을 의미합니다.

• 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.

2개의 깃발일 때, peaks 1, 5에 꽂을 수 있다.

3개의 깃발일 때, 1, 5, 10에 꽂을 수 있다.

4개의 깃발일 때, 1, 5, 10에 3개만 꽂을 수 있다.

return 3

 

제한조건

• 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].

N은 1~ 400,000 사이의 정수이다.

A 배열의 각각의 원소는 0 ~ 1,000,000,000 사이의 정수이다.

 

풀이를 어떻게 할지 막막해서.. 참고해봤다..( 아직 코드에 대한 이해가 필요함.. )

peak까지는 구하겠는데, 그 이후로는 방법이 생각나지 않는다...ㅠ

 

참고한 블로거님의 주소

https://coder-in-war.tistory.com/entry/Codility-Lesson10Medium-Flags

[ Codility ][Lesson10][Medium] Flags