[171120][Codility](C#)Flags

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

 

문제>

* 배열 A에서 0 < P < N - 1 && A[P-1] < A[P] > A[P+1] 인 값들을 찾아 Peak를 만든다.(중간중간 튀는 높은 값을 뽑으라는 소리)

* K는 플래그(깃발) 간의 간격이자 Peak에 설치가능한 최대 플래그(깃발) 수.

- K번째 플래그 사용시 두 플래그 사이의 거리는 K보다 커야한다.

* 플래그 사이간격은 절대값이다.

* 이때 최대 설치 가능한 플래그(깃발) 수를 구하라.

 

해결방법.

1) A[P-1] < A[P] > A[P+1]인  P를 담은 Peaks리스트를 생성.

*리스트 수가 3보다 작으면 위의 식이 성립 안되기 때문에 리스트 수를 리턴.

2) flags(깃발) 사이의 간격이자 최대 flags 수 K를 Peaks의 수와 같을 때 까지 flags 수를 증가하면서 검색.

- 내부에 반복문을 추가해 Peaks수 만큼 검색.

-(K는 2부터시작. 간격을 구해야 하기 때문. 이미 하나는 꽂고 시작하기 때문에 flags은 1부터 시작.)

- 만약, peak - next_peak(peak + 1)의 절대값이(간격) K보다 크거나 같으면 flags 수를 증가.

-peak은 현재의 next_peak로 변경(*간격조건이 맞은 next_peak부터 찾아야 하기 때문), next_peak는 peak + 1로 변경.

- 다르다면 다음 peak는 유지하고 next_peak를 증가.

- 만약 next_peak와 Peaks의 수가 같거나 꽂은 flags 수와 K가 같다면 반복을 멈춤.

- 만약, 받아놓은 flags 최대 수보다 이번에 꽂은 flags 수가 작다면 받아놓은 값 리턴.

- (줄어드는 시점부터 간격이 벌어질 수록 더 적게 꽂을 수 밖에 없다.)

- 아니라면 flags수와 기존 flags수 중 큰 값으로 갱신.

 

using System;
using System.Collections.Generic;
// you can also use other imports, for example:
// using System.Collections.Generic;

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

class Solution
{
    public int solution(int[] A)
    {
        // write your code in C# 6.0 with .NET 4.5 (Mono)
        if (A.Length < 3)
            return 0;

        List<int> Peaks = new List<int>();
        for (int i = 1; i < A.Length - 1; i++)
        {
            if (A[i] > A[i - 1] && A[i] > A[i + 1])
                Peaks.Add(i);
        }

        if (Peaks.Count < 3)
            return Peaks.Count;

        int output = 0;
        for (int K = 2; K <= Peaks.Count; K++)
        {
            int flags = 1;
            int peak = 0;
            int next_peak = 1;
            while (peak < Peaks.Count - 1)
            {
                if (Math.Abs(Peaks[peak] - Peaks[next_peak]) >= K)
                {
                    flags += 1;
                    peak = next_peak;
                    next_peak = peak + 1;
                }
                else
                    next_peak += 1;
                if (next_peak == Peaks.Count || flags == K)
                    break;
            }
            if (output > flags)
                return output;
            output = Math.Max(flags, output);
        }
        return output;
    }
}

 

 

 

 

17.11.20.(0200)

 

회고 : 해석은 K보다 크거나 같다고 해놓고는 코드로 클때만 체크해서 어마어마한 삽질 .ㅠ 코드가 깔금하진 못하다ㅠ