배열 A가 주어졌을 때, 배열의 모든 요소를 자신보다 오른쪽에 있는 값들 중 가장 큰 값으로 교체하고, 마지막 요소는 -1로 바꾸는 문제를 생각해 봅시다.
예를 들어 A = [5, 17, 40, 6, 3, 8, 2]라면 결과는 다음과 같습니다.
[40, 40, 8, 8, 8, 2, -1]
해결 접근 방법
이 문제는 배열을 오른쪽에서 왼쪽으로 한 번만 순회하면 O(n) 시간 복잡도로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 배열의 마지막 요소부터 왼쪽 방향으로 순회합니다.
- 변수 e를 -1로 초기화합니다. 이 값은 현재 위치 기준 오른쪽 구간의 최댓값을 저장합니다.
- i를 n-1부터 0까지 감소시키며 반복합니다.
- temp에 현재 e(오른쪽 최댓값)를 임시 저장합니다.
- e를 e와 array[i] 중 더 큰 값으로 갱신합니다.
- array[i]를 temp로 덮어씁니다.
- 순회가 끝나면 배열을 반환합니다.
이렇게 하면 각 위치에 해당 위치보다 오른쪽에 있는 값들의 최댓값이 순서대로 채워지고, 마지막 요소에는 초기값인 -1이 자연스럽게 남게 됩니다.
구현 예제
아래 C++ 코드를 통해 더 잘 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> replaceElements(vector<int>& arr) {
int rep = -1;
int n = arr.size();
for(int i = n - 1; i >= 0; i--){
int temp = rep;
rep = max(rep, arr[i]);
arr[i] = temp;
}
return arr;
}
};
main(){
Solution ob;
vector<int> c = {5,17,40,6,3,8,2};
print_vector(ob.replaceElements(c)) ;
}입력
[5, 17, 40, 6, 3, 8, 2]
출력
[40, 40, 8, 8, 8, 2, -1]
복잡도 분석
- 시간 복잡도: O(n) — 배열을 한 번만 순회하면 되므로 효율적입니다.
- 공간 복잡도: O(1) — 입력 배열을 그대로 수정(in-place)하기 때문에 추가 메모리가 거의 필요하지 않습니다.