Codility Lesson 10 - Peaks(JAVA)

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

Peaks coding task - Learn to Code - Codility

문제

- 비어 있지 않은 정수들로 이루어진 A배열이 주어진다.

- peak는 주변보다 큰 원소를 의미한다.( 0 < P < N − 1,  A[P − 1] < A[P] and A[P] > A[P + 1] )

- 예시 :

A[0] = 1 A[1] = 2 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 : 3, 5, 10

- peak를 1개 이상 포함하고, 같은 원소의 개수를 가진 block으로 나눌 때, 최대 몇개의 block으로 나눌 수 있는지를 구하라

• one block (1, 2, 3, 4, 3, 4, 1, 2, 3, 4, 6, 2). This block contains three peaks.
• two blocks (1, 2, 3, 4, 3, 4) and (1, 2, 3, 4, 6, 2). Every block has a peak.
• three blocks (1, 2, 3, 4), (3, 4, 1, 2), (3, 4, 6, 2). Every block has a peak. Notice in particular that the first block (1, 2, 3, 4) has a peak at A[3], because A[2] < A[3] > A[4], even though A[4] is in the adjacent block.

However, array A cannot be divided into four blocks, (1, 2, 3), (4, 3, 4), (1, 2, 3) and (4, 6, 2), because the (1, 2, 3) blocks do not contain a peak. Notice in particular that the (4, 3, 4) block contains two peaks: A[3] and A[5].

The maximum number of blocks that array A can be divided into is three.

 

- 3개로 나누었을 때가 최대로 return 3

 

제한조건

• N is an integer within the range [1..100,000];
• each element of array A is an integer within the range [0..1,000,000,000].

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

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

 

풀이

- A배열에서 peak를 구한다.

- block 최대 peak의 개수만큼 가능하다, 0 ~ peak의 개수만큼

- lo, mid, hi 값을 지정하여 이진탐색 구현 -> 값을 검증하는 부분 구현하다가 2시간 다보냄..

 

예외처리 부분 1개 맞음....

 

내일 다시 생각해서 구현해보기 어렵다 알고리즘...ㅠ

오늘까지 구현했던 소스코드

// 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 {
    int N;
    List<Integer> peaks;
    // List<Integer> factors;

    public int solution(int[] A) {
        // write your code in Java SE 8

        N = A.length;
        peaks = new ArrayList<>();
        // A가 2개 이하일때는 peak가 존재할 수 없다
        if( N < 3 ) return 0;

        // 1. peak 구하기
        // peak는 처음과 끝에는 존재할 수 없음
        for( int i=1; i<N-1; i++ ){
            if( A[i-1] < A[i] && A[i] > A[i+1] ){
                peaks.add(i);
                // System.out.println("peaks : " + i);
            }
        }

        if( peaks.size() == 0 ) return 0;   // peak가 존재하지 않을 경우

/*
        // 2. factor구하기
        factors = new ArrayList<>();
        for( int i=1; i<Math.sqrt(N); i++ ){
            if( N % i == 0 ){
                factors.add( i );
                factors.add( N / i );
                // System.out.println("i : " + i + " / N/i : " + (N/i));
            }
        }
        // factors.sort();
        Collections.sort(factors);
*/

        int lo = 0;
        int hi = peaks.size();
        int max = 0;

        while( lo <= hi ) {
            int mid = ( lo + hi ) / 2;
            System.out.println("mid : " + mid);
            if( check(mid) ){   // block에 각 peak가 들어간 경우
                
                lo = mid + 1;
                max = mid;
            }else{
                hi = mid - 1;
            }
        }

        return max;
    }

    // 각 block에 peak가 포함되는지를 확인하는 로직
    private boolean check( int num ){
        if( N % num != 0 ) return false;

        boolean result = false;
        int block = N / num;
        int index = block - 1;

        System.out.println("block : " + block);
        System.out.println("index : " + index);

        for( int i:peaks ){
            System.out.println("index : " + index + " / i : " + i);
            if( index >= i ){
                if( !result ){
                    index += block;
                }else{
                    continue;
                }
                result = true;
                
            }else{
                // peak가 존재하지 않는 경우
                result = false;
                break;   
            }
        }

        return result;
    }

}

 

4/29일 재도전 2트

- check 부분에서 검증할 수 있도록 코드 작성

- 예제 문제 풀이는 성공

 

같은날 재도전 3트

- 이진탐색을 굳이 할 필요 없이, check 메소드에서 factor가 아닌 경우에는 false를 리턴하게 만들었기에 peaks의 수를 for문을 거꾸로 돌리는 것으로 진행

드디어 풀었다ㅠㅠ 복잡할수록 간단히 생각해보기..

 

소스코드

// 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 {
    int N;
    List<Integer> peaks;

    public int solution(int[] A) {
        // write your code in Java SE 8
        N = A.length;
        peaks = new ArrayList<>();

        // 예외처리
        if( N < 3 ) return 0;   // peak가 있을 수 없음

        // 1. peak 구하기
        for( int i=1; i<N-1; i++ ){
            if( A[i-1] < A[i] && A[i] > A[i+1]){
                peaks.add(i);
                // System.out.println("peak : " + i);
            }
        }

        // peak가 없으면 block이 의미 없음
        if( peaks.size() == 0 ) return 0;

        // peak의 개수만큼만 block을 나눌 수 있음을 이용
        // 예제에서 peak는 [ 3, 5, 10 ] 3개
        int max = 0;
        for( int i=peaks.size(); i>=0; i-- ){
            if( check(i) ){
                max = i;
                break;
            }
        }

        return max;
    }

    private boolean check( int mid ){   // mid는 결국 block의 개수가 된다
        boolean result = false;
        if( N % mid != 0 ) return result;

        int prev_idx;
        int peak_idx = 0;
        int block = N / mid;
        int index = block - 1;
        for( int i=0; i<mid; i++ ){
            prev_idx = peak_idx;
            for( int j=peak_idx; j<peaks.size(); j++ ){
                if( peaks.get(j) <= index ){
                    peak_idx++;
                }else{
                    break;
                }
            }

            if( prev_idx == peak_idx ){
                result = false;
                break;
            }else{
                result = true;
                index += block;
            }
        }

        return result;
    }
}

 

다른분은 어떻게 풀었나궁금해서 참고한 블로그들

https://namget.tistory.com/entry/%EC%BD%94%EB%94%9C%EB%A6%AC%ED%8B%B0-Lesson-10-Peak

[코딜리티] - Lesson 10 Peak

 

https://deefer.tistory.com/124?category=826956 

Lesson10 - Peaks