C++ 프로그램: 중복 요소의 왼쪽 발생을 제거한 배열 구하기

n개의 요소로 이루어진 배열 A가 있다고 가정해 보겠습니다. 이 배열에서 중복된 요소를 제거하고, 각 요소에 대해서는 가장 오른쪽에 위치한 항목 하나만 남기려고 합니다. 단, 남겨진 고유 요소들의 상대적인 순서는 그대로 유지되어야 합니다.

예를 들어 입력이 A = [1, 5, 5, 1, 6, 1]이라면 출력은 [5, 6, 1]이 됩니다. 값 1은 세 번 등장하지만 가장 오른쪽에 있는 1만 남고, 값 5 역시 오른쪽에 있는 5만 남습니다.

해결 접근 방법

이 문제의 핵심 아이디어는 배열을 뒤에서부터 앞으로 순회하면서 처음 만나는 요소만 결과 배열에 저장하는 것입니다. 각 값의 등장 여부를 추적하기 위해 방문 표시(vis) 배열을 활용합니다. 뒤에서부터 탐색하면 자연스럽게 각 요소의 가장 오른쪽 발생이 먼저 기록되고, 이후 같은 값이 다시 나타나면 무시됩니다.

이를 위해 다음 단계를 따릅니다 −

크기가 1200인 두 배열 b와 vis를 선언
x := 0
n := A의 크기
i := n - 1부터 시작하여 i >= 0일 때까지 i를 1씩 감소시키며 반복:
    만약 vis[A[i]]가 0이라면:
        b[x] := A[i]
        x를 1 증가
        vis[A[i]] := 1
i := x - 1부터 시작하여 i >= 0일 때까지 i를 1씩 감소시키며 반복:
    b[i] 출력

C++ 구현 예제

더 나은 이해를 돕기 위해 다음 구현 코드를 살펴보겠습니다 −

#include <bits/stdc++.h>
using namespace std;

void solve(vector<int> A) {
    int b[1200], vis[1200], x = 0;
    int n = A.size();
    for (int i = n - 1; i >= 0; i--) {
        if (!vis[A[i]]) {
            b[x] = A[i];
            x++;
            vis[A[i]] = 1;
        }
    }
    for (int i = x - 1; i >= 0; i--)
        cout << b[i] << ", ";
}
int main() {
    vector<int> A = { 1, 5, 5, 1, 6, 1 };
    solve(A);
}

입력

{ 1, 5, 5, 1, 6, 1 }

출력

5, 6, 1,

동작 원리 및 복잡도

배열을 오른쪽에서 왼쪽으로 순회하면서 각 값을 처음 만날 때만 결과 배열 b에 추가합니다. vis 배열은 이미 처리된 값을 표시하여 중복 저장을 방지하는 역할을 합니다. 모든 순회가 끝나면 b에는 각 고유 값이 역순으로 저장되어 있으므로, 마지막에 b를 거꾸로 출력하면 원래 배열의 상대적 순서가 유지된 최종 결과를 얻을 수 있습니다.

이 알고리즘의 시간 복잡도는 O(n), 공간 복잡도는 O(n)입니다. 여기서 n은 배열의 길이를 의미합니다.