4. 정렬 (충남대 알고리즘 강의록)

충남대학교 컴퓨터공학과 이영석 교수님의 "알고리즘" 강의 실습 내용입니다.

• 실습 문제들의 코드 위주로 구성되어 있습니다.

문제 1: 버블정렬 §

#include <iostream>
#include <vector>
 
using namespace std;
 
void fnBubble(vector<char> vecIn, char& cAd, int& nCnt) {
	bool isChange = true;
	// 변경사항이 있고 정렬 횟수가 만료되지 않았을때까지 반복함
	while(isChange && nCnt > 0) {
		isChange = false;
 
		// 벡터의 첫 원소부터 n - 1 원소까지 탐색함
		for(auto it = vecIn.begin(); it < vecIn.end() - 1; it++) {
 
			// Ascending order 일때
			if(cAd == 'A') {
 
				// 앞의 원소가 더 크다면
				if(*it > *(it + 1)) {
 
					// 두 값을 스왑하고 변경되었음으로 변경함
					auto tmp = *it;
					*it = *(it + 1);
					*(it + 1) = tmp;
					isChange = true;
				}
 
			// Descending order 일때
			} else if(cAd == 'D') {
 
				// 앞의 원소가 더 작다면
				if(*it < *(it + 1)) {
 
					// 두 값을 스왑하고 변경되었음으로 변경함
					auto tmp = *it;
					*it = *(it + 1);
					*(it + 1) = tmp;
					isChange = true;
				}
			}
		}
 
		// 정렬 횟수를 1 감소시킴
		nCnt--;
	}
	for(auto el : vecIn) {
		cout << el << ' ';
	}
	cout << endl;
}
 
int main() {
	int nNum, nStep;
	char cAd;
	cin >> nNum >> nStep >> cAd;
	vector<char> vecIn(nNum);
	for(int i = 0; i < nNum; i++) {
		cin >> vecIn[i];
	}
	fnBubble(vecIn, cAd, nStep);
	return 0;
}

문제 2: 병합 정렬 §

#include <iostream>
#include <vector>
 
using namespace std;
 
int nStep;
char cAd;
 
// Subvector를 병합하는 함수
void fnMerge(vector<char>& vecIn, vector<char>& vecLeft, vector<char>& vecRight) {
	// 만약 정렬 횟수가 만료되면 이후에는 Left와 Right를 Concatenate하여 반환함
	if(nStep <= 0) {
		copy(vecLeft.begin(), vecLeft.end(), vecIn.begin());
		copy(vecRight.begin(), vecRight.end(), vecIn.begin() + vecLeft.size());
		return;
	}
 
	// 정렬 횟수가 만료되지 않았을 때
	auto lit = vecLeft.begin(), rit = vecRight.begin();
	u_long i = 0;
 
	// Left와 Right를 전부 iterate하여 타겟 벡터가 전부 채워질때까지 동작함
	while(lit < vecLeft.end() && rit < vecRight.end() && i < vecIn.size()) {
 
		// Ascending order이고 Left의 iterated element가 작을 경우
		//	 Left의 iterated element와 Right의 iterated element 중 더 작은 원소를 타겟 벡터에 먼저 넣어야 하므로
		//	 Left의 iterated element를 타겟 벡터에 넣는다.
		// Descending order이고 Left의 원소가 클 경우
		//	 Left의 iterated element와 Right의 iterated element 중 더 큰 원소를 타겟 벡터에 먼저 넣어야 하므로
		//	 Left의 iterated element를 타겟 벡터에 넣는다.
		if((cAd == 'A' && *lit < *rit) || (cAd == 'D' && *lit > *rit)) {
 
			// 원소를 타겟 벡터에 넣음
			vecIn[i] = *lit;
 
			// Left의 iterated element를 넣었으므로 left-iterator를 전진시킨다.
			// 타겟 벡터에 원소를 넣었으므로 타겟 벡터의 iterate index도 1 증가시킨다.
			lit++; i++;
 
			// 만약 Left에 더 이상 원소가 남아있지 않을 경우에는 Right에 남아있는 원소를 전부 타겟 벡터에 순서를 유지하여 넣어준다.
			if(lit >= vecLeft.end()) {
				copy(rit, vecRight.end(), vecIn.begin() + i);
				rit = vecRight.end();
			}
 
		// Ascending order이고 Right의 iterated element가 작을 경우
		//	 Left의 iterated element와 Right의 iterated element 중 더 작은 원소를 타겟 벡터에 먼저 넣어야 하므로
		//	 Right의 iterated element를 타겟 벡터에 넣는다.
		// Descending order이고 Right의 원소가 클 경우
		//	 Left의 iterated element와 Right의 iterated element 중 더 큰 원소를 타겟 벡터에 먼저 넣어야 하므로
		//	 Right의 iterated element를 타겟 벡터에 넣는다.
		} else if((cAd == 'A' && *lit > *rit) || (cAd == 'D' && *lit < *rit)) {
 
			// 원소를 타겟 벡터에 넣음
			vecIn[i] = *rit;
 
			// Right의 iterated element를 넣었으므로 right-iterator를 전진시킨다.
			// 타겟 벡터에 원소를 넣었으므로 타겟 벡터의 iterate index도 1 증가시킨다.
			rit++; i++;
 
			// 만약 Right에 더 이상 원소가 남아있지 않을 경우에는 Left에 남아있는 원쏘를 전부 타겟 벡터에 순서를 유지하여 넣어준다.
			if(rit >= vecRight.end()) {
				copy(lit, vecLeft.end(), vecIn.begin() + i);
				lit = vecLeft.end();
			}
		}
	}
 
	// 정렬 횟수를 1 감소시킴
	nStep--;
}
 
// Vector를 정렬하는 함수
void fnSort(vector<char>& vecIn) {
 
	// 벡터의 크기가 2보다 작을 때는 정렬되어 있는것으로 간주함.
	if(vecIn.size() < 2) { return; }
 
	// 백터를 두개의 subvector로 나눈다.
	int nSep = vecIn.size() / 2;
	vector<char> vecLeft, vecRight;
	vecLeft.assign(vecIn.begin(), vecIn.begin() + nSep);
	vecRight.assign(vecIn.begin() + nSep, vecIn.end());
 
	// Left subvector와 Right subvector를 재귀적으로 정렬해준다.
	fnSort(vecLeft); fnSort(vecRight);
 
	// 정렬이 끝난 Left subvector와 Right subvector를 병합한다.
	fnMerge(vecIn, vecLeft, vecRight);
}
 
int main() {
	int nNum;
	cin >> nNum >> nStep >> cAd;
	vector<char> vecIn(nNum);
	for(int i = 0; i < nNum; i++) {
		cin >> vecIn[i];
	}
	fnSort(vecIn);
	for(auto el : vecIn) {
		cout << el << ' ';
	}
	cout << endl;
	return 0;
}

문제 3: 그룹 애너그램 §

#include <iostream>
#include <map>
#include <deque>
#include <algorithm>
#include <string>
#include <sstream>
 
using namespace std;
 
int main() {
	string strTemp, strIn;
	deque< deque<string> > deqOut;
	map< string, deque<string> > mAns;
	
	getline(cin, strIn);
	stringstream ss(strIn);
 
	// 입력 문자열을 공백으로 구분하여 하나씩 꺼낸다.
	while(getline(ss, strTemp, ' ')) {
 
		// 단어 하나를 소문자로 변환한다.
		transform(strTemp.begin(), strTemp.end(), strTemp.begin(), ::tolower);
 
		// 해당 단어를 오름차순으로 정렬하여 strS에 저장한다.
		string strS = strTemp;
		sort(strS.begin(), strS.end());
 
		// map의 key에서 해당 단어를 조회하고 존재하지 않는다면 해당 단어를 포함하는 벡터를 할당해준다.
		if(mAns.find(strS) == mAns.end()) {
			mAns[strS] = {strTemp};
 
		// map의 key에 해당 단어가 이미 존재하면 연결되어있는 벡터에 해당 단어를 추가한다.
		} else {
			mAns[strS].push_back(strTemp);
		}
	}
 
	// map을 순회하며 각각의 key에 대칭되는 value인 anagram group을 오름차순으로 정렬한다.
	// 이후 anagram group을 2차원 데크에 추가한다.
	for(const auto& it : mAns) {
		auto deqGroup = mAns[it.first];
		sort(deqGroup.begin(), deqGroup.end());
		deqOut.push_back(deqGroup);
	}
 
	// anagram group들을 저장한 2차원 데크에서 각각의 그룹을 그룹의 첫번째 원소를 기준으로 정렬한다.
	sort(deqOut.begin(), deqOut.end(), [](deque<string> deq1, deque<string> deq2) {
		return deq1[0] < deq2[0];
	});
 
	for(const auto& deqGroup : deqOut) {
		for(auto it = deqGroup.begin(); it < deqGroup.end() - 1; it++) {
			cout << *it << ' ';
		}
		cout << *(deqGroup.end() - 1) << '\n';
	}
}