[백준알고리즘] 18870번: 좌표 압축 -C++

[백준알고리즘] 18870번: 좌표 압축 -C++

18870번: 좌표 압축 (acmicpc.net)

18870번: 좌표 압축

 

좌표 압축 문제를 풀었는데.. 오랜만에 푸느라 <algorithm> 헤더 관련해서 하나도 기억이 안 난다.

그래서 실버 등급 문제임에도 시간 초과로 인해 다른 글을 찾아보고 풀 수 있었다.

 

2가지 정도의 풀이 방법이 공유되고 있었는데, 그중 하나의 방법을 이용해서 문제를 해결했다.

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

---

문제 풀이

문제 자체는 쉬워 보였다. 입력되는 수들이 있을 때, 각각의 수보다 작은 수의 개수를 출력해주면 된다.

 

풀이 방법은 크게 다음과 같은 순서로 진행된다.

1. 순서대로 입력받기
2. 입력 값에 대한 중복 제거
3. 각 값보다 작은 수의 개수 확인
4. 순서대로 출력 하기

 

2번 과정인 값의 중복 제거는 간단하게 set을 이용해서 해결할 수 있었다. set 자체는 독립적인 값만 들어갈 수 있기 때문에 중복을 제거할 때 사용하기 좋다.

vector를 사용했기 때문에 sort와 unique를 사용하는 방법도 있다.

 

위의 과정 중에 3번 과정 때문에 애를 먹었다. 

 

인덱싱 해주는 과정은 <algorithm>의 lower_bound를 사용했다. lower_bound는 주어진 범위 내에서 주어진 값의 iterator를 반환해준다. 값을 찾을 때 이진 탐색을 사용해, 보다 빠르게 값을 찾을 수 있다. (단, 주어진 범위에 값이 정렬되어 있어야 한다.)

- lower_bound 참고 링크 : lower_bound - C++ Reference (cplusplus.com)

 

처음에는 set 자체의 lower_bound를 사용해서 유사하게 iterator 연산을 통해 set의 begin으로부터 얼마나 떨어져 있는지를 찾으려고 했다. 그런데 Syntax error가 발생해서 확인해보니, set의 iterator 끼리는 연산이 불가능하다고 한다.

산술 연산 가능한 "임의 접근 반복자"는 vector, deque 뿐이라고 한다.

- bidirectional iterator 참고 : https://stackoverflow.com/a/22171519

- stl 반복자 참고 : [C++ 표준] STL 반복자(+ 반복자의 종류 Iterator Category - 평생 공부 블로그 : Today I Learned‍ 🌙 (ansohxxn.github.io)

 

결국 <algorithm>의 lower_bound를 사용해 다른 사람들처럼 문제를 해결할 수 있었다.

 

알고리즘 공부 다시 해야겠다..^~^

 

 

#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>

int main(void) {
	/* 입력 */
	unsigned int uiNum;
	scanf("%u", &uiNum);

	std::vector<int> vecNum;
	std::set<int> mapNum;
	for ( unsigned int uiLoop = 0; uiLoop < uiNum; ++uiLoop ) {
		int iNum;
		scanf("%d", &iNum);

		vecNum.push_back(iNum);
		mapNum.insert(iNum);
	}

	std::vector<int> vecIndex;
	vecIndex.assign(mapNum.begin(), mapNum.end());

	/* 출력 */
	for ( std::vector<int>::iterator itNum = vecNum.begin(); itNum != vecNum.end(); ++itNum ) {
		// 인덱싱 값 출력
		printf("%d ", (int) (std::lower_bound(vecIndex.begin(), vecIndex.end(), *itNum) - vecIndex.begin()));
	}

	return 0;
}

---

아래는 시간 초과가 발생했던 코드다.

각 값보다 작은 수를 찾기 위해, map을 이용해 값 별로 인덱싱하는 과정이 추가되어 시간 초과가 발생했다.

#include <cstdio>
#include <list>
#include <set>
#include <map>

int main(void) {
	/* 입력 */
	unsigned int uiNum;
	scanf("%u", &uiNum);

	std::list<int> lstNum;
	std::set<int> mapNum;
	for ( unsigned int uiLoop = 0; uiLoop < uiNum; ++uiLoop ) {
		int iNum;
		scanf("%d", &iNum);

		lstNum.push_back(iNum);
		mapNum.insert(iNum);
	}

	/* 좌표별 더 작은 좌표값의 개수 할당 */
	unsigned int uiSmallerNum = 0;
	std::map<int, unsigned int> mapNumCnt;
	for ( std::set<int>::iterator itNum = mapNum.begin(); itNum != mapNum.end(); ) {
		const int iNum = *itNum;
		const unsigned int uiCnt = uiSmallerNum;

		mapNumCnt.insert(std::make_pair(iNum, uiCnt));

		uiSmallerNum++;
		mapNum.erase(itNum++);
	}

	/* 출력 */
	for ( std::list<int>::iterator itNum = lstNum.begin(); itNum != lstNum.end(); ++itNum ) {
		printf("%u ", mapNumCnt.find(*itNum)->second);
	}

	return 0;
}