💎 문제
수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.
Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.
X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.
💎 입력
첫째 줄에 N이 주어진다.
둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.
ex)
5
2 4 -10 4 -9
💎 출력
첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.
ex)
2 3 0 3 1
💎 제한
- 1 ≤ N ≤ 1,000,000
- -10^9 ≤ Xi ≤ 10^9
💎 풀이 방법
일단 문제부터 이해하기가 굉장히 어려웠는데,,,이해하고 나면 간단한 내용이다. 좌표가 N개 만큼 주어지면 그 N개의 좌표를 정렬하였을 때, 이전에 입력한 처음의 순서에서 그 정렬된 좌표들의 위치 인덱스를 출력하는 것이다.
예를 들면, 입력 값에서 2 4 -10 4 -9가 입력되었다면 정렬해보면 -10 -9 2 4 4가 될 것이며 중복되는 것을 제거한 후 정렬된 자리의 인덱스를 기억해서 이전 처음 좌표의 정렬된 인덱스인 2 3 0 3 1을 출력하면 되는 것이다!!
굉장히 큰 N의 값이 주어질 수도 있기 때문에 시간초과를 고려해야했고 정렬할때 비교하면서 인덱스의 위치를 확인해야하기 때문에 이분탐색과 같은 효율적인 정렬 알고리즘을 사용하면서 풀어야겠다는 생각이들었다!!...만 저번에 해시 문제를 풀었었기에 STL 클래스 map을 이용하여 풀은 문제이다!!
vector <int> v(N);
vector <int> resultV(N);
map <int,int> m;
for(int i = 0;i < N;i++){
cin >> v[i];
resultV[i] = v[i];
}vector 두 개와 map을 선언하여 사용하였다!! 하나의 벡터는 출력을 위해서 그대로 사용하게 될 좌표들이고 하나는 좌표들을 정렬하였을 때 인덱스 위치를 map에 넣어 줄 것이다. map을 이용하여 중복되는 값은 받지 않도록 할 것이며 출력할 때 map을 이용하여 처음 입력 받은 좌표들을 탐색해서 정렬된 상태에서의 인덱스들을 출력해줄 것이다!!
sort(v.begin(), v.end());
for(int i = 0;i < N;i++){
if(m.find(v[i]) == m.end()){
m.insert({v[i], n});
n++;
}
}
for(int i = 0;i < v.size();i++){
cout << m[resultV[i]] << " ";
}정렬된 v vecotr의 좌표들을 이용하여 map안에 존재하지 않다면 map안에 정렬된 vecotr의 key와 그의 인덱스를 value로 넣어주었다! 만약 중복되었다면 조건문에 의해 지나가서 처음 넣어준 좌표의 인덱스 만이 삽입될 것이다!
마무리 되었다면 출력해주는데 처음 상태의 vector 좌표 값을 map에서 찾아준 뒤 그에 해당하는 value를 출력해주면 끝난다!! 해시를 사용하니깐 간단하게 풀 수 있었다.
💎 전체 코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
int main(int argc, const char * argv[]) {
int N;
int n = 0;
cin >> N;
vector <int> v(N);
vector <int> resultV(N);
map <int,int> m;
for(int i = 0;i < N;i++){
cin >> v[i];
resultV[i] = v[i];
}
sort(v.begin(), v.end());
for(int i = 0;i < N;i++){
if(m.find(v[i]) == m.end()){
m.insert({v[i], n});
n++;
}
}
for(int i = 0;i < v.size();i++){
cout << m[resultV[i]] << " ";
}
return 0;
}💎 고민
map STL 클래스의 위력을 알 수 있는 문제였다. map을 사용하면서 푸느라 정렬되지 않은 vector와 정렬한 vector 두 개를 제자리에 사용하기 위해 헷갈리긴 했지만 이분 탐색을 새로 짜서 푸는 것보다 쉽게 풀 수 있었던 것 같다. 물론 이분 탐색이 STL 클래스를 이용하지 않고 시간 복잡도 효율이 더 좋을 수 있을 것 같지만 저번에 풀었던 해시 문제를 떠올려서 적용해볼 수 있었다!!
문제 이해가 상당히 어려워서 만약 코테에서 이러한 문제가 나왔을 때 당황하지 않고 이해하는 것이 중요할 것이라고 생각되었다... 문제를 차근차근히 읽고 입력값과 출력값을 잘 적용시켜보자. 문제가 길면 더 힘들 수 있으니 긴 문제를 이해하기 위해 프로그래머스 코테 문제도 풀어보자!!
화팅!!
