각 요소가 앞뒤 요소 개수를 나타내는 순열 찾기

이번 글에서는 흥미로운 배열 문제 하나를 살펴보겠습니다. 배열에 n개의 원소가 주어졌을 때, 각 원소가 자신의 앞 또는 뒤에 있는 원소의 개수를 나타내도록 배열을 재배치(순열)할 수 있는지 확인하는 것이 목표입니다.

예를 들어 배열이 {2, 1, 3, 3}이라고 가정해 보겠습니다. 이 경우 적절한 순열은 {3, 1, 2, 3}입니다.
· 첫 번째 3 → 자신 뒤에 세 개의 원소가 있음을 의미
· 1 → 자신 앞에 한 개의 원소가 있음을 의미
· 2 → 자신 앞에 두 개의 원소가 있음을 의미
· 마지막 3 → 자신 앞에 세 개의 원소가 있음을 의미

핵심 아이디어

인덱스 i(0부터 시작) 위치에 놓인 원소의 값은 반드시 다음 두 값 중 하나여야 합니다.

· i : 해당 위치 앞에 있는 원소의 개수
· n-i-1 : 해당 위치 뒤에 있는 원소의 개수

따라서 각 위치마다 가능한 값을 빈도 맵(frequency map)에서 차례로 확인해 사용하고, 더 이상 배치할 수 없는 경우가 발생하면 조건을 만족하는 순열이 존재하지 않는다고 판단하면 됩니다.

알고리즘

checkPermutation(arr, n)

시작
    각 숫자의 빈도를 저장할 해시맵을 정의한다 (키와 값은 모두 정수형)
    arr의 각 원소 e에 대해:
        map[e]를 1 증가
    i = 0부터 n-1까지 반복:
        만약 map[i]가 0이 아니면:
            map[i]를 1 감소   // i번째 위치 앞의 원소 개수로 사용
        아니고 map[n-i-1]이 0이 아니면:
            map[n-i-1]을 1 감소   // i번째 위치 뒤의 원소 개수로 사용
        아니면:
            false 반환
    true 반환
끝

C++ 구현 예제

#include<iostream>
#include<map>
using namespace std;
bool checkPermutation(int arr[], int n) {
    map<int, int> freq_map;
    for(int i = 0; i < n; i++){ //각 숫자의 빈도 계산
        freq_map[arr[i]]++;
    }
    for(int i = 0; i < n; i++){
        if(freq_map[i]){ //현재 위치 앞의 원소 개수로 사용
            freq_map[i]--;
        } else if(freq_map[n-i-1]){ //현재 위치 뒤의 원소 개수로 사용
            freq_map[n-i-1]--;
        } else {
            return false;
        }
    }
    return true;
}
main() {
    int data[] = {3, 2, 3, 1};
    int n = sizeof(data)/sizeof(data[0]);
    if(checkPermutation(data, n)){
        cout << \"순열이 존재합니다\";
    } else {
        cout << \"순열이 존재하지 않습니다\";
    }
}

실행 결과

순열이 존재합니다

복잡도 분석

빈도 저장과 조회에 균형 이진 탐색 트리 기반의 std::map을 사용하면 시간 복잡도는 O(n log n)이며, 해시 기반의 unordered_map을 사용하면 평균 O(n)으로 처리할 수 있습니다. 공간 복잡도는 서로 다른 값의 개수에 비례하여 최대 O(n)입니다.