[ Codility ][Lesson10][Medium] Flags

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

Flags coding task - Learn to Code - Codility

문제

 

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] = 2

has 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] = 2

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

접근

음 각 꼭짓점에 대해서 K 개의 flag를 놓으면서 두 꼭짓점 사이 간격이 K개를 넘지 않아야 하므로 이분탐색이 생각났다.

어떤 mid 값을 테스트해보면서 간격이 mid를 넘고, 안넘고를 처리해나가면 풀 수 있을 것 같았다.

 

근데 100이 뜨지 않고 중간에 틀린게 있어서 봤더니 list에 담는 전처리 과정에서 실수를 해서 디버깅에 다소(?) 시간이 걸렸다.

쉬워보이는 부분을 코딩한다 하더라도, 꼼꼼히 확인하는 습관을 들이자.

코드

/**
 * Codility Lesson 10 Midium Flags
 * 이분탐색
 */
import java.util.*;
public class L10_M_Flags {
    class Solution {
        int len;
        List<Integer> list;
        public int solution(int[] A) {
            // write your code in Java SE 8
            len = A.length;
            list = new ArrayList<>();

            for (int i = 1; i < len - 1; i++) {
                if (A[i - 1] < A[i] && A[i] > A[i + 1]) {
                    list.add(i);
                    i++;
                }
            }

            int lo = 0;
            int hi = list.size();
            if (hi < 2) return hi;

            int max = 0;
            while (lo <= hi) {
                int mid = (lo + hi) / 2;
                if (check(mid) == mid) {
                    lo = mid + 1;
                    max = mid;
                } else {
                    hi = mid - 1;
                }
            }

            return max;
        }

        private int check(int num) {
            int prev = list.get(0);
            int cnt = 1;
            for (int i = 1; i < list.size() && cnt < num; i++) {
                if (list.get(i) - prev >= num) {
                    cnt++;
                    prev = list.get(i);
                }
            }

            return cnt;
        }
    }
}