백준 10867 - 중복 빼고 정렬하기

문제링크

• 백준 10867

문제 접근

• 오름차순으로 정렬하면서 지우는 방법을 선택했다. 따라서 유연하게 메모리를 관리할 수 있는 벡터 컨테이너를 활용했다.
• 오름차순 함수를 정의할 때, 모든 원소를 비교하는 연산과정이 필요하다. 그 과정에서 본인보다 작은 원소를 찾으면 해당 원소와 자리를 바꾼다.
• 만약, 본인과 같은 원소를 찾으면 해당 원소를 벡터 컨테이너에서 지운다.
• 원소를 지우게 되면 벡터 컨테이너의 크기가 변하므로 반복문을 작성할 때 런타임 에러가 발생하지 않도록 주의해야 한다.

의사코드(pseudo-code)

# define function
- void sortAscend(vector<int> &v)
	- for i=0 to v.size()-2:
		- for j=i+1 to v.size()-1:
			- if v[i] > v[j]:
				- tmp = v[i]
				- v[i] = v[j]
				- v[j] = tmp
			- else if v[i] == v[j]:
				- v.erase(j)
				- j -= 1

# main
- cin >> N
- vector<int> v(N,0)
- for i=0 to N-1:
	- scanf("%d", &v[i])
- sortAscend(v)
- for i=0 to v.size()-1:
	- printf("%d ", v[i])

소스코드 및 분석

전체 코드

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

void sortAscend(vector<int>& v) {
	for (int i = 0; i < v.size() - 1; i++) {
		for (int j = i + 1; j < v.size(); j++) {
			if (v[i] > v[j]) {
				int tmp;
				tmp = v[i];
				v[i] = v[j];
				v[j] = tmp;
			}
			else if (v[i] == v[j]) {
				v.erase(v.begin() + j);
				j--;
			}
		}
	}
}

int main()
{
	int N;
	scanf("%d", &N);
	vector<int> v(N, 0);
	for (int i = 0; i < N; i++)
		scanf("%d", &v[i]);
	sortAscend(v);
	for (int i = 0; i < v.size(); i++)
		printf("%d ", v[i]);
}

• 함수 sortAscend() 에서, 반복문의 임계치를 v.size()로 설정했다. 배열에서 원소를 지우는 연산을 진행하면 배열의 전체 크기는 줄어드므로 반복문의 임계치 또한 유동적으로 변해야 런타임 에러를 피할 수 있다.
• v.erase() 를 호출할 때, 매개변수(parameter)는 반복자(iterator) 형태여야 한다. 벡터 컨테이너의 begin() 메서드를 호출하면 배열의 처음 주소를 가리키는 반복자를 반환받을 수 있다. 포인터 연산을 생각하면 해당 코드는 쉽게 이해할 수 있다.
• 원소를 지우고 다음 반복문 순환으로 넘어갈 때, 배열의 인덱스 j 보다 뒤에 원소들은 한칸씩 당겨진 형태가 되므로 j-1 을 해준 상태에서 다음 순환으로 넘어가야 원소를 놓치지 않고 탐색할 수 있다.

다른 풀이

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

bool cmp(const int& a, const int& b) {
	return a < b;
}
int main()
{
	int n;
	cin >> n;

	vector<int> v(n);
	for (int i = 0; i < n; i++)
		cin >> v[i];

	sort(v.begin(), v.end(), cmp);
	vector<int> ans;
	for (auto ele : v) {
		if (ans.empty()) ans.push_back(ele);
		if (ans.back() != ele) ans.push_back(ele);
	}
	for (auto ele : ans) {
		cout << ele << " ";
	}
	cout << endl;
	return 0;
}