백준 18870번 : 좌표 압축

문제 접근

---

처음에는 STL 의 set 이나 map 을 이용하려 했다. 자동으로 sort 되는 건 좋았지만, find 로 찾은 뒤 (해당 문자열 주소값) - (시작 주소값) 으로 인덱스를 출력하려고 하면 에러나서 이 문제에서 set 을 사용하지 않기로 했다. 에러는 iterator 여서 - 연산자 사용이 불가하는 것이었다.

 

그래서 vector 에 넣어서 sort 하고 unique 로 중복 제거한 뒤, 마찬가지로 주소값으로 접근했는데 실행은 잘 되지만 시간초과났다. set 에서는 주소값 계산이 안 됐는데 vector 에서는 돼서 왜 그런지 고민하고 찾아봤다.

 

C++ STL 에서 컨테이너는 크게 두 가지 종류가 있는데, 배열처럼 객체들을 순차적으로 보관하는 시퀀스 컨테이너(Sequence Container) 와 키를 바탕으로 대응하는 값을 찾아주는 연관 컨테이너(Associative Container)가 있다고 한다.

 

시퀀스 컨테이너에는 vector, list, deque 가 있고 원소들이 메모리 상에서 순차적으로 저장되어 있어 임의의 위치에 있는 원소를 매우 빠르게 접근할 수 있다. 예를 들면 우리가 vector v 의 5번째 원소 주소에 접근할 때 v.begin()+5 와 같이 접근 할 수 있는 것처럼 말이다.

 

그리고 set, map 과 같은 것들을 연관 컨테이너(associative container)라고 하는데, 모든 연관 컨테이너(set, multiset, map, multimap)는 노드 기반 컨테이너이기 때문에 데이터 여러개가 하나의 메모리 단위에 저장된다.

 

set 은 set 에 저장되어 있는 원소들에 접근하기 위해 반복자를 제공하는데 이 반복자가 Bidirectional Iterator 라고 하고 이 때문에 시퀀스 컨테이너처럼 임의의 위치에 있는 원소에 접근하는 것이 불가능하고 순차적으로 하나씩 접근해야 한다고 한다.

 

그럼 Bidirectional Iterator 가 뭘까? 이건 또 찾아보니까 STL 에서 제공하는 Iterator 의 종류 중 하나였는데 말 그대로 양방향 반복자라는 것이었다. 반복자의 종류의 기능 포함 관계는 다음과 같았다.

 

임의 접근 반복자( Random Access Iterator; vector, deque의 반복자 ) > 양방향 반복자( Bidirectional Iterator; 연관 컨테이너의 반복자 ) > 순방향 반복자( Forward Iterator ) > 입력 반복자( Input Iterator ), 출력 반복자( Output Iterator )

 

따라서 계산이 불가능했던 이유는 set 이 데이터를 하나의 메모리 단위에 저장해서 임의의 위치에 있는 원소에 접근이 불가능하기 때문이라고 할 수 있을 것 같다.

 

 

문제 코드 ( 시간 초과 )

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void)
{
	int N, input;
	vector<int> seq;
	vector<int> sorted;
	
	
	cin>>N;
	
	for(int i=0; i<N; ++i)
	{
		cin>>input;
		seq.push_back(input);
	}
	
	sorted = seq;
	sort(sorted.begin(),sorted.end());
	sorted.erase(unique(sorted.begin(),sorted.end()),sorted.end());
	
	for(int i=0; i<N; ++i)
	{
		cout<<find(sorted.begin(),sorted.end(),seq[i])-sorted.begin()<<' ';
	}
	cout<<'\n';
}

시간 복잡도 계산해보니 O(N^2logN) 인 것 같다. ( find 함수가 O(NlogN) 이다. )

 

 

문제 코드 ( 맞았습니다 )

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void)
{
	int N, input, prior=0;
    // first 에 좌표 저장, second 에 입력 순서 저장.
	vector<pair<int,int>> seq;
	
	cin>>N;
	// 압축 좌표를 저장할 배열.
	int ans[N];
	
	for(int i=0; i<N; ++i)
	{
		cin>>input;
		seq.push_back(make_pair(input,i));
	}
	
	sort(seq.begin(), seq.end());
	
	for(int i=0; i<N-1; ++i)
	{
    	// 현재 좌표와 다음 좌표가 다르다면 압축 좌표 +1.
        // ans 배열에 입력 순서에 맞는 index 에 압축 좌표를 넣는다.
		if(seq[i].first!=seq[i+1].first)
			ans[seq[i].second] = prior++;
		else
			ans[seq[i].second] = prior;
	}
	
	ans[seq[N-1].second] = prior;
	
	for(int i=0; i<N; ++i)
	{
		cout<<ans[i]<<' ';
	}
	cout<<'\n';
}

 

참고 자료

---

https://modoocode.com/223

씹어먹는 C++ - <10 - 1. C++ STL - 벡터(std::vector), 리스트(list), 데크(deque)>

https://modoocode.com/224

씹어먹는 C++ - <10 - 2. C++ STL - 셋(set), 맵(map), unordered_set, unordered_map>

http://tcpschool.com/cpp/cpp_iterator_category

코딩교육 티씨피스쿨