Codility Java Peaks

문제

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");

import java.util.List;
import java.util.ArrayList;

class Solution {
  public int solution(int[] A) {
    List<Integer> peaks = getPeaks(A);
    for (int idx = A.length; idx >= 1; idx--) {
      if (A.length % idx == 0) {
        int blockSize = A.length / idx;
        int blockCount = 0;
        for (int peakIndex : peaks) {
          if (peakIndex / blockSize == blockCount) {
            blockCount++;
          }
        }
        if (blockCount == idx) {
          return blockCount;
        }
      }
    }
    // If A cannot be divided into some number of blocks, the function should return 0.
    return 0;
  }
  private List<Integer> getPeaks(int[] A) {
    List<Integer> peaks = new ArrayList<>();
    for (int idx = 1; idx < A.length - 1; idx++) {
      if (A[idx - 1] < A[idx] && A[idx] > A[idx + 1]) {
        peaks.add(idx);
      }
    }
    return peaks;
  }
}

설명

1. 우선 봉우리가 될 수 있는 위치를 먼저 계산하여 변수 peaks에 저장한다.
   • 봉우리가 될 수 있는 기본 조건은 해당 높이가 전후 높이보다 커야 한다.
   • 특정 위치에 봉우리가 될 수 있는지가 중요하므로, 배열이 아니라 컬렉션으로 인덱스만 저장한다.
2. 반복문을 통해서 봉우리를 포함하여 나눌 수 있는 최대 블록의 수를 구한다.
   • 동일한 숫자의 블록으로 나눠야 하므로, 주어진 배열 A의 크기와 블록의 수를 표현하는 idx를 나눈 값이 정수인 경우에만 확인한다.
   • 봉우리의 위치를 저장한 변수 peaks를 반복하여 동일한 숫자의 블록이 가능한지 계산을 하고, 가능한 블록의 숫자가 확인되면 해당 값을 주어진 문제의 결과로 반환한다.
3. 반복이 끝나면 동일한 숫자의 블록으로 나눌 수 없다는 의미이므로, 0을 주어진 문제의 결과로 반환한다.

결과

Link

소스

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