[JAVA] Plateau Length 구하기 알고리즘

2번째 문제는 Plateau length를 구하는 알고리즘이다. 사실 이 문제는 필수문제는 아니었지만 나의 알고리즘 실력은 아직 부족하여... 연습삼아 하기로 결정했다.

먼저 Plateau를 사전에 검색하면 안정기 또는 정체 상태라는 뜻으로 나온다. 따라서 한 배열에서 연달아 나오는 숫자들중 그 길이가 가장 큰 값을 반환하면 될 것 같다.

먼저 주어진 문제는 다음과 같다.

The method

public static int maxPlateauLength (int[] a)

shall calculate the length of the longest plateau in an array a of ascending or

descending numbers. A plateau is a sub-array containing at each index the same

value. 

아래는 예시가 주어져 있다.

For array

a = {8,8,7,7,4,4,4,3,3,3,3,2,2,2,2,1}

the method should return result 4 (plateau with value 3 from index 5 to 8) and for

array b = {1,2,4,6} the result 1.

a 배열에선 숫자 3이 4개 들어있으므로 값 4를 반환시키면 되고 b 배열에선 모든 숫자가 하나씩 있으니 1이 가장 큰 길이의 값이다 고로 1을 반환한다.

자 그럼 문제를 보자.

a) Write a simple and efficient implementation! 

-> 코드를 짜라는것 같다... (감과 단어에 의존한 해석)

b) Does it have an advantage that the values are sorted? Would your algorithm also

work if the values in the field were not sorted?

이건 배열이 정렬이 되었던 것에 대해서 묻는 것이다. 

-> 배열이 정렬이 되었던것에 대해서 편리했는가? 만약 정렬이 되어있지 않는다 해도 알고리즘이 작동을 할 까? 라는 해석이 되겠다.

그럼 내가 생각한 알고리즘은 어떻게 될까... 

처음에 생각한건 현재 숫자를 세는 count라는 변수와 가장 큰 값을 저장하는 max라는 변수를 선언한다. 배열을 탐색해가며 count에 저장을 한다. 탐색해 가다가 다른 숫자를 만나면 현재까지 count된 값과 max값을 비교하여 더 큰 값으로 max값을 초기화 한다. (물론 가장 처음 탐색할땐 count가 max값이랑 같은 값을 가진다.)

처음에는 되게 쉽다고 생각하며 코딩을 했는데 템플릿에 올라온 배열이 {1,1,1,1} 이런 배열이 있었다... 심지어 문제 b에서 말했듯이 정렬이 되지 않은 알고리즘에선 제대로된 값을 반환하지 못했다.. ㅠㅠ

수 많은 수정 끝에 마침내 코드를 작성했다.

public static int plateauLength(int[] a) {

int count = 1; // start with 1

int max = 1; // start with 1

int length = a.length; // allocate length of array a

Arrays.sort(a); // sorting

for (int k=1; k<length; k++) // start comparing elements

{

if (a[k-1] == a[k]) //same

{

count++; // count

if (max<count) //max is smaller than count

max=count; // allocate max value as count

}

else //different

{

if (max<=count) // count is larger than max

{

max=count; // save max as count value

count=1; // initialize

}

else

count=1; // initialize

}

}

return max; //return max value

}

 결국 정렬 없이는 짜기 힘들었다고 판단해서 결국 가장 먼저 정렬을 해주고 시작했다.

주어진 템플릿은 다음과 같다.

public static final int MAX_LEN = 100000000;

/** some simple tests */

public static void main(String[] args) {

int[] f1 = {1, 2, 2, 3, 4, 4, 4, 4, 5, 5, 6 };

System.out.println("longest plateau in f1: " + plateauLength(f1));

System.out.println("  expected: 4");

System.out.println();

int[] f2 = {9, 9, 9, 9, 9, 4, 4, 4, 3, 2, 2, 2, 2 };

System.out.println("longest plateau in f2: " + plateauLength(f2));

System.out.println("  expected: 5");

System.out.println();

int[] f3 = {1, 2, 3, 4, 5, 6 };

System.out.println("longest plateau in f3: " + plateauLength(f3));

System.out.println("  expected: 1");

System.out.println();

int[] f4 = {1, 1, 1, 1};

System.out.println("longest plateau in f4: " + plateauLength(f4));

System.out.println("  expected: 4");

System.out.println();

//generate sortedarray of random values

Random rnd = new Random(42);

int[] f5 = new int[MAX_LEN];

int limit = (int)Math.sqrt(MAX_LEN);

for (int i = 0; i < f5.length; i++) {

f5[i] = rnd.nextInt(limit);

}

Arrays.sort(f5);

System.out.println("length of array f5:" + f5.length);

System.out.println("length of longest plateau in f5: " + plateauLength(f5));

System.out.println();

int[] f6 = {2, 2, 1, 3, 1};

System.out.println("longest plateau in f6: " + plateauLength(f6));

System.out.println("  expected: 2");

System.out.println();

System.out.println("- fertig -");

}

}