Codility Java Flags

문제

Link

코드

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
  public int solution(int[] A) {
    int result = 0;
    boolean[] peaks = getPeaks(A);
    int[] nextPeaks = getNextPeaks(peaks);
    for (int idx = 1; idx < A.length; idx++) {
      if (isPossibleToSetOnPeak(nextPeaks, idx)) {
        result = Math.max(result, idx);
      }
    }
    return result;
  }
  private boolean[] getPeaks(int[] A) {
    boolean[] peaks = new boolean[A.length];
    for (int idx = 1; idx < A.length - 1; idx++) {
      if (A[idx] > A[idx - 1] && A[idx] > A[idx + 1]) {
        peaks[idx] = true;
      }
    }
    return peaks;
  }
  private int[] getNextPeaks(boolean[] peaks) {
    int[] nextPeaks = new int[peaks.length];
    int nextPeak = -1;
    for (int idx = nextPeaks.length - 1; idx >= 0; idx--) {
      if (peaks[idx]) {
        nextPeak = idx;
      }
      nextPeaks[idx] = nextPeak;
    }
    return nextPeaks;
  }
  private boolean isPossibleToSetOnPeak(int[] nextPeaks, int point) {
    int index = 0;
    for (int idx = 0; idx < point; idx++) {
      if (index >= nextPeaks.length || nextPeaks[index] < 0) {
        return false;
      }
      index = nextPeaks[index] + point;
    }
    return true;
  }
}

설명

1. 우선 봉우리가 될 수 있는 위치를 먼저 계산하여 배열 peaks에 저장한다.
   • 봉우리가 될 수 있는 기본 조건은 해당 높이가 전후 높이보다 커야 한다.
2. 봉우리가 될 수 있는 위치를 기반으로 다음 봉우리의 위치를 계산하여 배열 nextPeaks에 저장한다.
   • 봉우리가 될 수 있는 위치를 역순으로 반복을 수행하여 다음 봉우리의 위치를 임시 저장하고, 직전 봉우리에서 해당 위치를 사용하면 된다.
3. 저장한 다음 봉우리의 위치를 기반으로 최종 봉우리의 개수를 계산하여 주어진 문제의 결과로 반환한다.
   • 반복을 통해서 다음 봉우리가 존재하지 않거나, 다음 봉우리가 현재 위치보다 더 멀 경우 깃발을 꽃을 수 없다.

결과

Link

소스

Sample Code는 여기에서 확인 가능합니다.