3. 복잡도, 완전탐색 (충남대 알고리즘 강의록)

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

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

문제 1: 애너그램 판별하기 §

#include <iostream>
#include <map>
#include <algorithm>
 
using namespace std;
 
/**
 * 입력받은 두 문자열에 대해 anagram이 맞는지 판별하는 함수
 */
string anagram(string strInput1, string strInput2) {
	map<char, int> mapRes1, mapRes2;
	transform(strInput1.begin(), strInput1.end(), strInput1.begin(), ::tolower); // 첫번째 문자열을 소문자로 바꿈
	transform(strInput2.begin(), strInput2.end(), strInput2.begin(), ::tolower); // 두번째 문자열을 소문자로 바꿈
	for(auto cEl : strInput1) { // 첫번째 문자열을 순회함
		if(mapRes1.find(cEl) != mapRes1.end()) { // map에 문자가 존재하면 1을 증가
			mapRes1[cEl]++;
		} else { // map에 문자가 존재하지 않으면 1을 할당
			mapRes1[cEl] = 1;
		}
	}
	for(auto cEl : strInput2) { // 두번째 문자열을 순회함
		if(mapRes2.find(cEl) != mapRes2.end()) { // map에 문자가 존재하면 1을 증가
			mapRes2[cEl]++;
		} else { // map에 문자가 존재하지 않으면 1을 할당
			mapRes2[cEl] = 1;
		}
	}
	return mapRes1 == mapRes2 ? "True" : "False"; // 두 map이 동일한지 검사하여 그에 맞는 문자열을 반환
}
 
int main() {
	string strInput1, strInput2;
	cin >> strInput1 >> strInput2;
	cout << anagram(strInput1, strInput2) << endl;
	return 0;
}

문제 2: 가장 긴 팰린드롬 판별하기 §

#include <iostream>
 
using namespace std;
 
/**
 * 입력받은 문자에 대해 Longest Palindromic Substring을 반환하는 함수
 */
string fnLPS(string& strInput) {
	string strMax = "";
	for(auto it = strInput.begin(); it < strInput.end(); it++) { // 입력 문자열의 첫번째 문자부터 순회함
		if(it + 2 < strInput.end() && *it == *(it + 2)) { // "aba"처럼 가운데 문자 하나를 두고 양옆의 문자가 동일한 경우
			auto l = it, r = it + 2; // 첫번째 포인터를 동일한 문자의 왼쪽 문자를 가르키게 하고, 두번째 포인터를 동일한 문자의 오른쪽 문자를 가르키게 함
			// 첫번째 포인터와 두번째 포인터가 가르키는 문자가 동일하는 한 두 포인터를 양쪽으로 확장시킴
			while(strInput.begin() <= l && r < strInput.end() && *l == *r) { l--;r++; }
			strMax = strMax.size() < static_cast<u_int>(r - l - 1) ? strInput.substr(l + 1 - strInput.begin(), r - l - 1) : strMax;
			// 첫번째 포인터와 두번째 포인터 사이에 있는 substring의 길이가 strMax보다 크다면 해당 substring으로 갱신함
		}
		if(it + 1 < strInput.end() && *it == *(it + 1)) { // "aa"처럼 동일한 문자 두개가 연속으로 등장하는 경우
			auto l = it, r = it + 1; // 첫번째 포인터를 동일한 문자의 왼쪽 문자를 가르키게 하고, 두번째 포인터를 동일한 문자의 오른쪽 문자를 가르키게 함
			// 첫번째 포인터와 두번째 포인터가 가르키는 문자가 동일하는 한 두 포인터를 양쪽으로 확장시킴
			while(strInput.begin() <= l && r < strInput.end() && *l == *r) { l--;r++; }
			strMax = strMax.size() < static_cast<u_int>(r - l - 1) ? strInput.substr(l + 1 - strInput.begin(), r - l - 1) : strMax;
			// 첫번째 포인터와 두번째 포인터 사이에 있는 substring의 길이가 strMax보다 크다면 해당 substring으로 갱신함
		}
	}
	return strMax; // 결과로 나온 substring을 반환함
}
 
int main() {
	string strInput;
	cin >> strInput;
	cout << fnLPS(strInput) << endl;
	return 0;
}

문제 3: 다트 점수 계산하기 §

#include <iostream>
#include <regex>
#include <vector>
 
using namespace std;
 
/**
 * "\d+[SDT]형태의 문자열을 숫자로 바꾸는 함수"
 */
int fnCount(string strCur) {
	int nRes = 0;
	int nNum = stoi(strCur.substr(0, strCur.size() - 1)); // 마지막 문자만 뺀 나머지를 숫자로 변환함
	switch(strCur[strCur.size() - 1]) { // 마지막 문자에 대해 switch문을 이용함
		case 'S' :
		nRes = nNum; // S로 끝날때는 그대로 반환
		break;
		case 'D' :
		nRes = nNum * nNum; // D로 끝날때는 제곱을 반환
		break;
		case 'T' :
		nRes = nNum * nNum * nNum; // T로 끝날때는 세제곱을 반환
		break;
	}
	return nRes;
}
 
int dart(string strInput) {
	strInput += "0T"; // 마지막에 *가 들어올 경우에도 동일하게 이전과 이후의 값을 2배 해주는 로직을 사용하기 위해 0의 값을 추가함
	regex re("\\d+S|\\d+D|\\d+T|[*#]"); // 사용한 정규식
	auto it = sregex_iterator(strInput.begin(), strInput.end(), re); // 정규식으로 매칭된 문자열을 순회하는 반복자 선언
	vector<int> vecRes; // 각 라운드의 결과를 담는 벡터
	while(it != sregex_iterator()) { // 반복자가 끝까지 갈때까지 순회함
		string strCur = (*it).str(), strNext = ""; // 현재 매칭된 문자열을 strCur에 저장함(strNext는 사용하지 않은 변수)
		switch(strCur[strCur.size() - 1]) {
			case '*' :
			*(vecRes.end() - 1) *= 2; // *일 경우 벡터의 마지막 원소를 2배 해줌
			it++; // 반복자를 1 전진시킴
			vecRes.push_back(fnCount((*it).str())); // 1 전진시킨 반복자에 매칭되는 문자열을 fnCount로 점수로 변환하고 벡터에 push함
			*(vecRes.end() - 1) *= 2; // 방금 push한 원소를 2배 해줌
			break;
			case '#' :
			*(vecRes.end() - 1) *= -1; // #일 경우 벡터의 마지막 원소의 부호를 바꿔줌
			break;
			default :
			vecRes.push_back(fnCount(strCur)); // *나 #가 아닐때는 매칭된 문자열을 fnCount를 통해 점수로 변환해 벡터에 push함
			break;
		}
		it++;
	}
	int nRes = 0;
	for(auto el : vecRes) { // 각 라운드의 결과를 총합해 반환
		nRes += el;
	}
	return nRes;
}
 
int main() {
	string strInput;
	cin >> strInput;
	cout << dart(strInput) << endl;
 
	return 0;
}