문제
해당 문제는 B[ P[i] ] = A[i] 관계에 따라 주어진 배열 A를 오름차순으로 만드는 수열 P를 출력하는 문제이다.
문제 이해를 위해 차근히 생각해보면 다음과 같이 생각할 수 있다.
1) 배열 A의 성분들을 오름차순으로 정렬하고, 이를 배열 B와 mapping 한다.
ex.
B[0] = A[2]
B[1] = A[0]
B[2] = A[1]
2) B[ P[i] ] = A[i] 관계에 따라 P[i] = i 이므로, 이를 통해 수열 P를 완성한다.
ex.
P[0] = 1
P[1] = 2
P[2] = 0
즉, 수열 P의 각 값은 배열 A의 각 성분이 정렬했을 때, 몇 번째 위치에 오는지를 의미하게 된다.
이때, 주의할 점은 크기가 같은 수열의 원소가 여러 개가 존재하면 사전순으로 앞서는대로(순서를 반영해서) 정렬해야 한다는 것이다.
해당 문제를 풀기 위해 sort 함수와 map 자료구조를 사용했다.
먼저, 입력을 받는 vector와 입력 값을 정렬하기 위해 사용할 vector를 각각 선언했다.
그리고 sort 함수를 통해 vector를 오름차순 정렬한 다음, vector의 인덱스를 key, 값을 value로 하여 map 자료구조에 삽입하였다.
마지막으로 for 문을 통해 입력을 받은 vector(정렬되지 않은 원본)를 탐색하며, vector의 값과 map의 value 값이 일치하는지 탐색한다.
이때, 일치하는 값을 찾으면 해당 자료의 key값을 결과값을 저장하는 vector에 삽입하고, 중복 탐색을 피하기 위해 value 값을 -1로 바꿔준다.
이렇게 하면 중복된 숫자에 대해서도 입력 순서를 고려하면서 배열 A의 각 성분들이 정렬 시 몇 번 위치에 오는지 출력할 수 있다.
map 자료구조를 사용한 이유로는 정렬됐을때 순서(인덱스) 값이 필요했기 때문이다.
물론 글을 쓰고 있는 지금 다시 생각해보면, 굳이 map 자료구조를 사용하지 않고 입력값이 저장된 vector를 정렬된 vector에 대해 탐색하면서 값을 수정&저장해도 괜찮았을 것 같다.
map 자료구조를 사용한 경우, 각 탐색에 대해 O(logN)이 소요되므로, 전체 시간복잡도는 O(NlogN)이 되고, map 자료구조를 사용하지 않은 경우에는 O(N^2)으로 구현할 수 있다.
위의 내용을 정리한 전체 코드는 다음과 같다.
//map 자료구조 사용
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <map>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
//freopen("input.txt", "rt", stdin);
int n;
cin >> n;
vector<int> a(n);
vector<int> temp(n);
vector<int> sol;
map<int, int> table;
map<int, int>::iterator it;
for (int i = 0; i < n; i++) {
cin >> a[i];
temp[i] = a[i];
}
sort(temp.begin(), temp.end());
for (int i = 0; i < n; i++) {
table[i] = temp[i];
}
for (int i = 0; i < n; i++) {
for (it = table.begin(); it != table.end(); it++) {
if (it->second == a[i]) {
sol.push_back(it->first);
it->second = -1;
break;
}
}
}
for (int i = 0; i < n; i++) {
cout << sol[i] << ' ';
}
cout << "\n";
return 0;
}//map 자료구조 사용X
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <map>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
//freopen("input.txt", "rt", stdin);
int n;
cin >> n;
vector<int> a(n);
vector<int> temp(n);
vector<int> sol;
map<int, int> table;
map<int, int>::iterator it;
for (int i = 0; i < n; i++) {
cin >> a[i];
temp[i] = a[i];
}
sort(temp.begin(), temp.end());
for (int i = 0; i < n; i++) {
table[i] = temp[i];
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (temp[j] == a[i]) {
sol.push_back(j);
temp[j] = -1;
break;
}
}
}
for (int i = 0; i < n; i++) {
cout << sol[i] << ' ';
}
cout << "\n";
return 0;
}