개요
이 튜토리얼에서는 배열에서 인접한 두 요소가 같을 때 앞쪽 요소를 두 배로 만들고, 생긴 빈자리를 0으로 채운 뒤, 모든 0을 배열의 끝으로 이동시키는 C++ 프로그램을 작성해 보겠습니다.
문제 접근 방법
이 문제는 다음 세 단계로 해결할 수 있습니다.
- 두 배로 만들기: 인접한 두 인덱스의 값이 서로 같고 0이 아닌 경우, 앞쪽 요소를 두 배로 만들고 뒤쪽 요소를 0으로 변경합니다.
- 0 채우기: 두 배로 만든 후 생긴 자리를 0으로 채웁니다.
- 0 이동하기: 배열 내 모든 0을 배열의 끝으로 이동시킵니다. 이때 0이 아닌 요소들의 상대적인 순서는 그대로 유지됩니다.
예시
입력 배열이 {2, 3, 3, 4, 0, 5, 5}라면 처리 과정은 다음과 같습니다.
- 인덱스 1과 2의 값 3, 3이 같으므로 → 6, 0으로 변경
- 인덱스 5와 6의 값 5, 5가 같으므로 → 10, 0으로 변경
- 배열이 {2, 6, 0, 4, 0, 10, 0}이 되고, 0을 모두 뒤로 이동하면 최종 결과는 {2, 6, 4, 10, 0, 0, 0}입니다.
C++ 구현 코드
전체 코드를 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
// 0이 아닌 요소를 앞쪽으로 옮기고 나머지를 0으로 채우는 함수
void moveZeroesToEnd(int arr[], int n) {
int count = 0;
for (int i = 0; i < n; i++) {
if (arr[i] != 0) {
arr[count++] = arr[i];
}
}
while (count < n) {
arr[count++] = 0;
}
}
// 인접한 같은 요소를 두 배로 만들고 0을 뒤로 이동하는 함수
void updateAndRearrangeArray(int arr[], int n) {
if (n == 1) {
return;
}
for (int i = 0; i < n - 1; i++) {
if ((arr[i] != 0) && (arr[i] == arr[i + 1])) {
arr[i] = 2 * arr[i];
arr[i + 1] = 0;
i++;
}
}
moveZeroesToEnd(arr, n);
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}
int main() {
int arr[] = { 2, 3, 3, 4, 0, 5, 5, 0 }, n = 7;
cout << "Given Array: ";
printArray(arr, n);
cout << endl;
updateAndRearrangeArray(arr, n);
cout << "Updated Array: ";
printArray(arr, n);
cout << endl;
return 0;
}실행 결과
위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.
Given Array: 2 3 3 4 0 5 5 Updated Array: 2 6 4 10 0 0 0
코드 설명
updateAndRearrangeArray 함수는 배열을 한 번 순회하면서 현재 요소와 다음 요소가 같고 0이 아닌 경우 현재 요소를 두 배로 만들고 다음 요소를 0으로 설정합니다. 이때 i++를 통해 바로 다음 요소를 건너뛰므로 연속된 중복이 잘못 처리되는 것을 방지할 수 있습니다.
moveZeroesToEnd 함수는 0이 아닌 요소들을 배열 앞쪽부터 차례대로 배치한 후, 남은 자리를 모두 0으로 채웁니다. 이 방식은 시간 복잡도 O(n), 공간 복잡도 O(1)로 매우 효율적입니다.
마무리
이 튜토리얼에서는 배열의 인접한 중복 요소를 두 배로 만들고 0을 배열 끝으로 이동하는 방법을 알아보았습니다. 궁금한 점이 있다면 댓글로 남겨주세요!