CF R #695_B 복습

B. Hills And Valleys

문제 설명

n개의 정수배열이 주어진다. 배열의 원소들을 a1, a2, ..., an 으로 부른다고 하자. 이때 임의의 정수 j ( 2 <= j <= n-1) 에 대해 aj > aj-1, aj > aj+1을 만족하는 경우 aj를 언덕, aj < aj-1, aj < aj+1 을 만족하는경우 aj를 계곡이라고 부르자.
배열이 주어졌을 때 문제를 푸는 사람은 단 하나의 a를 골라 원하는 값으로 바꿀 수 있다. (바꾸지 않을 수도 있다)
이상의 조건하에서 n개의 정수배열이 주어졌을 때 배열에서 언덕의 수과 계곡의 수의 합이 가장 작은 경우의 값을 출력하시오.

예시

입력

6
1 6 2 5 2 10

출력

1

5를 2로 바꿈으로써 언덕 1개만을 남길 수 있다.

나의 풀이과정

얼만큼 계곡과 언덕의 수를 줄일 수 있는가?

문제를 푸는 사람은 단 하나의 a를 바꿀수 있다. 한 점을 바꾸어서 영향을 받는 것은 선택된 a와 양옆의 a 이다. 예시에서 보이듯이 한 점으로 최대 3개의 언덕 또는 계곡의 수를 줄일 수 있다 (편의상 언덕이라는 용어로 통일하겠습니다). 그러나 언덕수를 항상 3만큼 줄일 수 있는 것은 아닌데, 다음과 같은 a 패턴이 나올 때 그렇다.

이와 같이 주어진 a의 패턴에 따라 0~3개의 언덕수를 줄일 수 있다. 따라서 각각의 a를 변경함으로서 몇개의 언덕수를 줄일 수 있는지를 확인하고 가장 크게 줄어드는 경우에서의 언덕수를 구해야 한다.

어떠한 패턴이 있을까?

1. aj-1 == aj+1 인 경우
   aj 에 aj-1를 대입함으로써 aj-1, aj, aj+1를 언덕이 아니게 만들 수 있다. aj를 바꾸기 전에 aj-1, aj, aj+1 가 언덕인지 확인하여 얼만큼의 언덕을 줄일 수 있는지 확인할 수 있다.
2. aj-1 != aj+1 인 경우
   나타날 수 있는 패턴은 대략 다음과 같다.
   
   aj-1 < aj+1 인경우의 그림이지만, 반대의 경우는 그림을 뒤집으면 위 그림에서 똑같은 경우를 생각할 수 있다.

문제를 쉽게 풀기 위한 꼼수

배열에 대해 언덕 여부를 파악하는 것은 시간이 얼마 들지 않는다. 따라서 더 생각할 필요 없이, aj를 언덕의 패턴이 유의미하게 변화하는 1) ~ 5) 에 위치시키고 언덕여부를 판단해서 aj를 변화시켰을 때 나올 수 있는 가장 적은 언덕수를 구할 수 있다.
여기서 조금더 생각해보면 1), 3), 5)는 검사할 필요가 없다. 각 점들에 대해 언덕이 발생할 수 있는 경우를 정리하면 다음과 같다.

여기서 2), 4) 의 경우를 생각해보면 모든 경우에 대해서 항상 1), 3), 5)보다 언덕수가 적거나 같은 결과가 나온다는 것을 알 수 있다. 따라서 2), 4)에 aj를 위치시켰을 때 (aj = aj+1, aj = aj-1)의 경우만 계산하면 된다.

느낀점

위의 해결방법을 떠올릴 때 까지도 마냥 쉬운 것은 아니었지만, 문제를 풀기 위한 코드를 구현하다 보면 상당히 실수할만한 부분이 많다. 아래는 내가 실수했을 때의 코드이다.

for(int i=2; i<n+2; i++){
    int bf=0,n1=0,n2=0;
    if (hill_or_vally(arr[i-1], arr[i], arr[i+1])){
        cnt++;
    }
    for(int j=i-1;j<i+2;j++){
        if(hill_or_vally(arr[j-1],arr[j],arr[j+1])){
            bf++;
        }
        if(hill_or_vally(arr[j-1],arr[j-1],arr[j+1])){
            n1++;
        }
        if(hill_or_vally(arr[j-1],arr[j+1],arr[j+1])){
            n2++;
        }
    }
    n1 = min(n1, n2);
    best = max(best, bf-n1);
}

바꾸기전, 2)번에 옮긴경우, 4)번에 옮긴경우를 체크하기 위해 위와 같은 코드를 사용했다. 중간에 보면 arr[j]의 위치를 j-1, j+1로 바꾼 것을 알 수 있는데 이것은 aj의 언덕여부를 판별할 때는 문제가 되지 않지만 aj-1, aj+1의 언덕여부를 판별할 때는 문제가 된다. aj만 옮겼을 때의 언덕수를 세야하는데 aj-1, aj+1도 2), 4)에 옮겼을 때의 언덕여부를 체크하게 되기 때문이다.
코딩테스트의 시간제한 특성상 코드의 무결성을 깊게 생각하기 어려워서 이런 실수가 자주 발생하는 것 같다. 최근에는 풀이가 복잡한 문제의 경우 코드를 부분별로 나눠서 테스트를 진행하는데, 급할수록 돌아가라고 꼼꼼하게 코드를 작성하는 것이 결국에는 시간이 절약되는 것 같다.