10.11 Peak과 Valley

문제 

정수 배열에서 peak란 현재 원소가 인접한 정수보다 크거나 같을 때를 말하고, 'valley'란 현재 원소가 인접한 정수보다 작거나 같을 때를 말한다. 예를 들어 {5,8,6,2,3,4,6}이 있으면, {8,6}은  peak고 {5,2}는 valley인 것이다. 

정수배열이 주어졌을때 'peak'와 'valley'가 번갈아 등장하도록 정렬하는 알고리즘을 작성하라.

 

해법

1. 부분 최적 해법

 배열을 정렬하고 위치를 바꿈으로써 peak와 valley를 순차적으로 나올 수 있도록 만들 수 있을 것이다.

정렬된 배열 0 1 4 7 8 9 가 있다고 하자. 

0은 올바른 위치고 

1은 잘못 놓였다 0과 4중에 자리를 바꿀 수 있으나 0와 바꿔보자 

7도 잘못 놓였다. 4과 8중에 자리를 바꿀 수 있으나 4과 바꿔보자 

9도 잘못 놓였다 8과 자리를 바꿀 수 있으니 8과 바꿔보자 

그러면 0 4 1 8 7 9로 peak와 valley가 번갈아 나타나는 배열이 나타난다.

이 알고리즘의 TimeComplexity = O(NlogN)이다.

def sortValleyPeak(array):
    array.sort()
    for i in range(1,len(array)):
        array[i] , array[i+1] = array[i+1] , array[i]

2. 최적 해법

저 알고리즘보다 더 최적이되려면 정렬을 하지 말아야한다. 

그냥 배열을 가지고는 peak와 valley가 번갈아 나오도록 만들 수 없는 걸까?

9 1 0 4 8 7 이라는 배열이 있다고 가정하자.

그전에 더 짧은 배열을 통해 규칙을 확인해보자 

0 1 2 라는 배열이 있을때 

0 2 1  ->peak

1 0 2

1 2 0  ->peak

2 1 0 

2 0 1

나머지 배열도 수정해서 peak가 되게 할 수 있을까?

가운데 원소와 인접한 원소 중에 가장 큰수와 바꾸면 된다.

"두 원소를 맞바꿨을때 이전에 처리했던 수열의 규칙이 깨지는 경우가 있지는 않을까?" -> 이문제에서 중간값과 왼쪽 값을 바꾼다고 했을때 왼쪽값은 여전히 valley일 것이다 중간 값이 왼쪽 값보다 작으므로 더 작은 수를 놓게 되기 때문이다. 

def bigIndex(array, a,b,c):
    len_a = len(array)
    a = array[a] if a>=0 and a < len_a else - int('inf')
    b = array[b] if b>=0 and b < len_a else - int('inf')
    c = array[c] if c>=0 and c < len_a else - int('inf')

    max_num = max(a,b,c)
    if array[a] == max_num :
        return a
    elif array[b] == max_num :
        return b
    else :
        return c