[백준] 18870. 좌표 압축 (C++)

Level

Silver2

 

Idea

이 문제에서 생각해야할 것은 두가지이다.

1. 중복되는 좌표를 어떻게 제거할 것인가?

2. 어떠한 수보다 작은 수의 개수를 어떻게 셀것인가?

문제를 풀고 다른 사람들의 코드를 봤는데 대부분 lower_bound 함수를 사용하셨더라. 하지만 난 lower_bound에 대해 몰랐어서 map을 사용했다. 자동정렬 된다는 점과 키값이 중복을 허용하지 않는다는 특징때문에 map을 골랐다.

내 풀이 방식의 핵심 포인트는 다음과 같다. 예를 들어 원소가 1 3 5 7 9 이렇게 있다면 3보다 작은 수의 개수는 3의 인덱스값인 1이다. 그러니까 map을 이용해서 key값에 입력값을 넣고 value에 인덱스를 넣어주면 끝이다. 맵이 알아서 중복을 제하고 정렬을 해주니까 다른 부분은 건드리지 않아도 된다.

 

나중에 보려고 적는 삽질 기록..

'나보다 작은 수'를 어떻게 찾을지 고민을 많이 했다. 단순히 생각하면 이중포문으로 i+1 ~ n-1 범위를 탐색해서 찾아낼 수 있지만, 이 문제에서는 이중포문을 사용하지 못한다. 처음엔 map 하나로 모든걸 해결하고자했다. 그런데 map은 중복키가 허용되지 않는다는 문제가 있었다. 그래서 중복값을 넣을 수 있는 multimap을 쓰거나 vector pair을 써볼까 생각하기도 했다. 하지만 이 둘은 a[b]++ 같은 연산을 할 수 없는 문제가 있었다. 그래서 입력값의 순서와 중복값을 보존할 수 있는 벡터를 따로 만들어줘야겠다는 생각을 했다. 꼭 하나로 해결하려고 하는 습관을 고치려고 노력하는데 아직 안 되는 것 같다...

 

Key Point

시간복잡도 생각을 해야한다. 질문 게시판을 보면 알겠지만, 이 문제에서 가장 신경써야할 부분은 시간복잡도이다. 입력 개수가 백만개이므로 이중포문은 사용하지 못한다. 나는 엉뚱한 부분에서 시간초과가 걸렸다. 계속 1%에서 시간초과가 걸렸는데 코드가 간단해서 의심할 부분이 operator[] 연산자밖에 없었다. 졸지에 operator[] 연산자의 위험성에 대해 공부도 해보고 코드를 갈아엎을까 고민하기도 했다. 그런데 원인은 "endl"였다.....;;

 

 

Code

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

int n = 0;
vector<int>v;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);


	int input = 0;

	map<int, int>mp;

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> input;
		v.push_back(input);
		mp.insert({ input,0 });
	}


	int i = 0;

	for (pair<int, int>p : mp) {
			mp[p.first] = i++;
	}

	for (auto a : v) {
		cout << mp[a] << "\n";
	}

	return 0;
}