문제 개요
초기 배열 arr가 주어졌다고 가정해 봅시다. 매일 이전 날의 배열을 기반으로 새로운 배열을 생성하며, i번째 날에는 다음 규칙에 따라 (i-1)번째 날의 배열을 변환하여 i번째 날의 배열을 만듭니다.
- 어떤 요소가 왼쪽과 오른쪽 양쪽 인접 값보다 모두 작으면(국소 최솟값), 해당 요소를 1 증가시킵니다.
- 어떤 요소가 왼쪽과 오른쪽 양쪽 인접 값보다 모두 크면(국소 최댓값), 해당 요소를 1 감소시킵니다.
- 첫 번째 요소와 마지막 요소는 항상 그대로 유지됩니다.
이 과정을 며칠간 반복하면 더 이상 변화가 없는 안정 상태에 도달하게 됩니다. 우리의 목표는 이 최종 배열을 구하는 것입니다.
예를 들어, 초기 배열이 [6,2,3,4]라면 결과는 [6,3,3,4]입니다. 첫째 날에 배열은 [6,2,3,4]에서 [6,3,3,4]로 한 번 변경된 후, 이후에는 어떤 연산도 수행되지 않습니다.
해결 접근 방법
이 문제는 시뮬레이션 방식으로 해결할 수 있습니다. 배열에 변화가 발생하는 동안 계속해서 변환을 반복하고, 더 이상 변화가 없으면 반복을 종료합니다. 구체적인 단계는 다음과 같습니다.
- 배열의 크기가 2 이하라면 첫 번째와 마지막 요소만 존재하므로 변환이 일어나지 않습니다. 배열을 그대로 반환합니다.
- 변경 여부를 추적하는 플래그(flag)를 true로 설정합니다.
- 플래그가 true인 동안 다음을 반복합니다:
- 플래그를 false로 초기화합니다.
- 임시 배열 temp를 만들고 arr[0]을 삽입합니다.
- i를 1부터 (배열 크기 - 2)까지 반복하면서:
arr[i] < arr[i-1]이고arr[i] < arr[i+1]이라면 temp에arr[i]+1을 삽입하고 플래그를 true로 설정합니다.- 그렇지 않고
arr[i] > arr[i-1]이고arr[i] > arr[i+1]이라면 temp에arr[i]-1을 삽입하고 플래그를 true로 설정합니다. - 위 조건에 해당하지 않으면
arr[i]를 그대로 temp에 삽입합니다.
- arr의 마지막 요소를 temp에 삽입합니다.
- temp 배열로 arr을 갱신합니다.
- 더 이상 변화가 없으면 arr을 반환합니다.
C++ 구현 예제
다음 코드를 통해 실제 동작을 더 자세히 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define push push_back
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> transformArray(vector<int>& arr) {
if(arr.size()<=2)return arr;
bool flag = true;
while(flag){
flag = false;
vector <int> temp;
temp.push_back(arr[0]);
for(int i = 1; i < arr.size()-1; i++){
if(arr[i]< arr[i-1] && arr[i]<arr[i+1]){
temp.push(arr[i]+1);
flag = true;
}
else if(arr[i]> arr[i-1] && arr[i]>arr[i+1]){
flag = true;
temp.push(arr[i]-1);
}
else temp.push(arr[i]);
}
temp.push_back(arr[arr.size()-1]);
arr = temp;
}
return arr;
}
};
main(){
Solution ob;
vector<int> v = {1,6,3,4,3,5};
print_vector(ob.transformArray(v));
}실행 결과
입력:
[1,6,3,4,3,5]
출력:
[1,4,4,4,4,5]
동작 원리 분석
입력 배열 [1,6,3,4,3,5]의 변화 과정을 살펴보겠습니다.
- 첫 번째 반복에서 6은 양옆(1, 3)보다 크므로 5로 감소하고, 4는 양옆(3, 3)보다 크므로 3으로 감소합니다. 결과:
[1,5,3,3,3,5] - 두 번째 반복에서 5는 양옆(1, 3)보다 크므로 4로 감소합니다. 결과:
[1,4,3,3,3,5] - 세 번째 반복에서 4는 양옆(1, 3)보다 크므로... 실제로는 좌우 비교에 따라 점진적으로 값이 조정되며, 마지막에는
[1,4,4,4,4,5]에 도달해 더 이상 변화가 없습니다.
이처럼 매 반복마다 국소 극값들이 중앙값 쪽으로 평탄화되면서 결국 인접한 요소들 사이에 증가 또는 감소가 교차하는 형태(오르내림이 번갈아 나타나는 지그재그 패턴)에 도달하면 알고리즘이 종료됩니다. 시간 복잡도는 O(n²)이며, n은 배열의 길이입니다. 각 반복에서 배열 전체를 순회하기 때문입니다.