Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++에서 배열을 회문으로 만들기 위한 최소 병합 연산 횟수 구하기

이 문제에서는 n개의 양의 정수로 이루어진 배열 arr[]가 주어집니다. 우리의 목표는 이 배열을 회문(palindrome)으로 만들기 위해 필요한 최소 병합(merge) 연산 횟수를 구하는 것입니다.

회문 배열이란?

회문 배열은 회문 문자열과 유사한 개념입니다. 인덱스 i와 n-i-1에 위치한 요소들이 서로 같아야 하며, 예를 들어 {5, 1, 7, 2, 7, 1, 5}처럼 양쪽 끝에서 중앙으로 이동하며 비교했을 때 모든 값이 일치하는 배열을 의미합니다.

문제 설명

배열에 적용할 수 있는 유일한 연산은 병합 연산입니다. 병합 연산이란 인접한 두 요소, 즉 인덱스 i와 i+1의 값을 더해 하나의 요소로 합치는 것을 말합니다. 이 연산만을 반복해서 주어진 배열을 회문으로 만들어야 하며, 그때 필요한 최소 연산 횟수를 반환해야 합니다.

입력 및 출력 예시

입력

arr[] = {4, 1, 7, 6, 1, 5}

출력

2

설명

총 2번의 병합 연산이 필요합니다.

먼저 인덱스 0과 1의 요소를 병합하면 배열은 {5, 7, 6, 1, 5}가 됩니다.
이어서 인덱스 2와 3의 요소를 병합하면 배열은 {5, 7, 7, 5}가 되어 회문이 완성됩니다.

해결 접근 방법

이 문제는 투 포인터(two pointer) 기법을 활용하면 효율적으로 해결할 수 있습니다. 배열의 시작을 가리키는 start 포인터와 끝을 가리키는 end 포인터를 두고, 두 포인터가 만나거나 교차할 때까지(start == end) 아래 조건에 따라 연산을 수행합니다.

  • arr[start] == arr[end]인 경우: 현재 위치에서 회문 조건을 만족하므로 start는 1 증가(start++), end는 1 감소(end--)시켜 안쪽으로 이동합니다.

  • arr[start] > arr[end]인 경우: 끝쪽 값이 작으므로 end 위치에서 병합 연산을 수행하고, 병합 횟수(mergeCount)를 1 증가시킵니다.

  • arr[start] < arr[end]인 경우: 시작쪽 값이 작으므로 start 위치에서 병합 연산을 수행하고, 병합 횟수(mergeCount)를 1 증가시킵니다.

모든 비교가 끝난 후 누적된 병합 횟수를 반환하면 정답이 됩니다. 이 알고리즘의 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적입니다.

C++ 구현 코드

#include <iostream>
using namespace std;

int findMergeCount(int arr[], int n){
    int mergeCount = 0;
    int start = 0;
    int end = n - 1;
    while (start <= end) {
        if (arr[start] == arr[end]) {
            start++;
            end--;
        }
        else if (arr[start] > arr[end]) {
            end--;
            arr[end] += arr[end + 1];
            mergeCount++;
        } else {
            start++;
            arr[start] += arr[start - 1];
            mergeCount++;
        }
    }
    return mergeCount;
}

int main(){
    int arr[] = {4, 1, 7, 6, 1, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "배열을 회문으로 만들기 위해 필요한 최소 병합 연산 횟수는 " << findMergeCount(arr, n);
    return 0;
}

출력 결과

배열을 회문으로 만들기 위해 필요한 최소 병합 연산 횟수는 2

마무리

투 포인터를 사용해 배열 양끝에서부터 값을 비교하고, 더 작은 쪽을 인접 요소와 병합해 나가는 방식이 핵심입니다. 이렇게 하면 불필요한 탐색 없이 선형 시간 안에 최소 병합 연산 횟수를 정확히 구할 수 있으며, 코딩 테스트나 면접에서 자주 등장하는 대표적인 배열 조작 문제 유형이니 꼭 익혀두시길 바랍니다.