[백준알고리즘] 10867번: 중복 빼고 정렬하기 -C++

[백준알고리즘] 10867번: 중복 빼고 정렬하기 -C++

10867번: 중복 빼고 정렬하기 (acmicpc.net)

10867번: 중복 빼고 정렬하기

사실 이번 문제는 굉장히 쉬운 문제다. 정렬 알고리즘이라고 해서 풀려고 했는데, 너무 민망할 정도의 문제다. 그래서 글을 따로 작성하지 않으려다가 그냥 기록용으로 남긴다.

---

문제 풀이

문제에서 요구하는 조건 중에 주목할 것은 오름차순 정렬과 중복을 제거하는 것이다.

 

가장 먼저 생각이 든 것은 C++의 set를 이용하는 방식이다. set는 JAVA의 HashSet과 유사한 개념이다. 내부적으로는 RB Tree를 사용하는 것으로 알려졌다.

RB Tree는 균형 이진 탐색 트리의 종류로 검색/삽입/삭제에 걸리는 시간 복잡도가 모두 \( O(log\ n) \) 이다.

 

그래서 최대로 주어진 수의 크기만큼 입력이 들어고 출력을 한다고 하더라도 충분히 커버가 가능하다.

 

아래는 통과한 코드다.

#include <cstdio>
#include <set>

int inputSize();
std::set<int> inputSet(const int iSize);
void printSet(const std::set<int> &mapNumbers);

int main(void) {
	int iSize = inputSize();
	std::set<int> mapNumbers = inputSet(iSize);
	printSet(mapNumbers);
}

int inputSize() {
	int iSize = 0;
	scanf("%d", &iSize);
	return iSize;
}

std::set<int> inputSet(const int iSize) {
	std::set<int> mapNumbers;
	for ( int iCnt = 0; iCnt < iSize; ++iCnt ) {
		int iNum = 0;
		scanf("%d", &iNum);
		mapNumbers.insert(iNum);
	}
	return mapNumbers;
}

void printSet(const std::set<int> &mapNumbers) {
	for ( std::set<int>::const_iterator itNum = mapNumbers.begin(); itNum != mapNumbers.end(); ++itNum ) {
		printf("%d ", *itNum);
	}
}