문제 개요
요소들로 구성된 배열 a[]가 주어졌을 때, 각 요소가 마지막으로 등장한 시점을 기준으로 해당 요소들을 출력하는 것이 이번 문제의 목표입니다. 단순히 중복된 요소를 제거하는 것을 넘어, 배열 내에서 각 요소가 마지막으로 나타난 순서(상대적인 순서)까지 그대로 유지해야 합니다.
예를 들어 중복 값을 포함한 6개 요소의 배열 {1, 3, 2, 3, 1, 2}가 있다고 가정해 보겠습니다. 각 요소의 마지막 출현 순서를 기준으로 출력하면 결과는 3 1 2가 되어야 합니다.
예시
입력: a[]={4,2,2,4,1,5,1}
출력: 2 4 5 1알고리즘
이 문제는 STL의 unordered_map을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 먼저 배열을 한 번 순회하면서
unordered_map에 각 요소와 그 요소가 나타난 마지막 인덱스를 저장합니다. 같은 값이 여러 번 나타나면 인덱스가 계속 갱신되므로, 순회가 끝나면 맵에는 자연스럽게 최종(마지막) 인덱스만 남게 됩니다. - 다시 배열을 처음부터 순회하면서, 현재 인덱스 i가 맵에 저장된 해당 요소의 마지막 인덱스와 일치하는 경우에만 출력합니다. 이렇게 하면 중복은 제거되면서도 마지막 출현 기준의 원래 순서가 유지됩니다.
START
Step 1-> 함수 void printelements(int a[], int n) 선언
STL unordered_map ele 사용
Loop For int i=0 and i main()
배열 a[]={4,2,2,4,1,5,1} 선언
int n=sizeof(a)/sizeof(a[0]) 선언
printelements(a,n) 호출
STOP 구현 예제
#include <bits/stdc++.h>
using namespace std;
void printelements(int a[], int n) {
unordered_map<int, int> ele;
// 각 요소의 마지막 인덱스를 맵에 저장
for (int i = 0; i < n; i++)
ele[a[i]] = i;
// 현재 인덱스가 마지막 출현 인덱스와 일치할 때만 출력
for (int i = 0; i < n; i++) {
if (ele[a[i]] == i)
cout << a[i] << " ";
}
}
int main() {
int a[] = { 4,2,2,4,1,5,1 };
int n = sizeof(a) / sizeof(a[0]);
printelements(a, n);
return 0;
}실행 결과
위 프로그램을 실행하면 다음과 같은 출력이 생성됩니다.
2 4 5 1
동작 방식 살펴보기
입력 배열 {4, 2, 2, 4, 1, 5, 1}에서 각 요소의 마지막 출현 인덱스는 다음과 같습니다.
- 4 → 인덱스 3
- 2 → 인덱스 2
- 1 → 인덱스 6
- 5 → 인덱스 5
두 번째 순회에서 현재 인덱스와 마지막 출현 인덱스가 일치하는 요소는 순서대로 2(인덱스 2), 4(인덱스 3), 5(인덱스 5), 1(인덱스 6)이므로 최종 출력은 2 4 5 1이 됩니다.
시간 복잡도
unordered_map의 삽입과 조회는 평균 O(1)이므로, 전체 시간 복잡도는 배열을 두 번 순회하는 O(n)입니다. 공간 복잡도는 서로 다른 요소의 개수에 비례하여 최악의 경우 O(n)입니다.