[2021.04.01] 모의테스트

2019 코딩테스트를 사용하여 모의테스트 해봄. 4.5개 정도 풀었으나... 부족한 점이 보임

• 부족한 점, 알아둬야할 점 정리해서 시험보기 전 보충하기!

1번

#include <iostream>
#include <map>
#include <vector>
#include <sstream>

using namespace std;

map<string, string> lastNameMap;

vector<string> split(string input, char delimiter) {
	vector<string> answer;
	stringstream ss(input);
	string temp;

	while (getline(ss, temp, delimiter)) {
		answer.push_back(temp);
	}

	return answer;
}

void initLastNameMap(vector<string>& record)
{
	for (int i = 0; i < record.size(); i++) {
		vector<string> words = split(record[i], ' ');
		if ((words[0] == "Enter") || (words[0] == "Change")) {
			lastNameMap[words[1]] = words[2];
		}
	}
}
//sdfdfdfssdfsdfsdfdf
string translate(string record)
{
	string result = "";
	vector<string> words = split(record, ' ');
	if (words[0] == "Enter") {
		result = lastNameMap[words[1]] + "님이 들어왔습니다.";
	}
	else if (words[0] == "Leave") {
		result = lastNameMap[words[1]] + "님이 나갔습니다";
	}
	else {
		// Do nothing
	}
	return result;
}

vector<string> solution(vector<string>& record)
{
	vector<string> answer;

	initLastNameMap(record);

	for (int i = 0; i < record.size(); i++) {
		answer.push_back(translate(record[i]));
	}

	return answer;
}

int main()
{
	vector<string> record = {
		"Enter uid1234 Muzi",
		"Enter uid4567 Prodo",
		"Leave uid1234",
		"Enter uid1234 Prodo",
		"Change uid4567 Ryan"
	};

	vector<string> result = solution(record);

	cout << result[0] << endl;
	
	return 0;
}

2번

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct FailRate {
	int stage;
	double rate;
};

bool compare(FailRate a, FailRate b)
{
	if (a.rate > b.rate)
		return true;

	if (a.rate == b.rate) {
		if (a.stage < b.stage) {
			return true;
		}
	}

	return false;
}

double getRate(int n, int curStage, vector<int>& stages)
{
	int numOfPlayers = 0;
	int numOfFail = 0;

	for (int i = 0; i < stages.size(); i++) {
		if (stages[i] >= curStage) {
			numOfPlayers++;
		}
		if (stages[i] == curStage) {
			numOfFail++;
		}
	}

	if (numOfPlayers == 0)
		return 0;

	return numOfFail / double(numOfPlayers);
}

void calcFailRate(int n, vector<int>& stages, vector<FailRate>& failRates)
{
	for (int stage = 1; stage <= n; stage++) {
		double rate = 0;
		rate = getRate(n, stage, stages);
		failRates.push_back({stage, rate});
	}
}

vector<int> solution(int n, vector<int> stages)
{
	vector<FailRate> failRates;
	vector<int> result;

	calcFailRate(n, stages, failRates);
	sort(failRates.begin(), failRates.end(), compare);

	for (int i = 0; i < failRates.size(); i++) {
		result.push_back(failRates[i].stage);
	}

	return result;
}

int main()
{
	int n = 5;
	vector<int> stages = { 2, 1, 2, 6, 2, 4, 3, 3 };
	vector<int> result = solution(n, stages);

	for (int i = 0; i < result.size(); i++) {
		cout << result[i] << endl;
	}

	return 0;
}

3번

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

vector<int> path;
int numOfRows, numOfCols;

int isUniquePath(vector<vector<string>>& relation, vector<int> &path)
{
	vector<string> keys;

	for (int row = 0; row < numOfRows; row++) {
		vector<string> rowStrs = relation[row];
		string key = "";
		for (int i = 0; i < path.size(); i++) {
			key += rowStrs[path[i]];
		}
		keys.push_back(key);
	}

	int originSize = keys.size();
	sort(keys.begin(), keys.end());
	keys.erase(unique(keys.begin(), keys.end()), keys.end());
	int uniqueSize = keys.size();

	if (originSize == uniqueSize) {
		return true;
	}

	return false;
	
}

int dfs(vector<vector<string>>& relation, int preIdx)
{
	if (path.size() != 0) {
		if (isUniquePath(relation, path)) {
			return 1;
		}
	}

	int sum = 0;
	for(int i = preIdx +1 ; i < numOfCols ; i++) {
		path.push_back(i);
		sum += dfs(relation, i);
		path.pop_back();
	}

	return sum;
}

int solution(vector<vector<string>>& relation)
{
	numOfRows = relation.size();
	numOfCols = relation[0].size();

	int answer = dfs(relation, -1);
	cout << answer << endl;

	return answer;
}

int main()
{
	vector<vector<string>> relation = {
		{"100", "ryan", "music", "2"},
		{"200", "apeach", "math", "2"},
		{"300", "tube", "computer", "3"},
		{"400", "con", "computer", "4"},
		{"500", "muzi", "music", "3"},
		{"600", "apeach", "music", "2"},
	};

	int answer = solution(relation);

	return 0;
}

4번

#include <iostream>
#include <vector>
#include <list>

using namespace std;

struct Food {
	int num;
	int restTime;
};

list<Food> foods;

void initFoods(vector<int> &foodTimes)
{
	for (int i = 0; i < foodTimes.size(); i++) {
		foods.push_back({ i + 1, foodTimes[i] });
	}
}

int eatFoodsUntil(int k)
{
	auto foodIt = foods.begin();
	for (int i = 0; i < k; i++) {
		foodIt->restTime--;
		if (foodIt->restTime == 0)
			foodIt = foods.erase(foodIt);
		else
			foodIt++;

		if (foodIt == foods.end()) {
			foodIt = foods.begin();
		}
	}

	return foodIt->num;
}

int solution(vector<int> foodTimes, int k)
{
	initFoods(foodTimes);
	return eatFoodsUntil(k);
}

int main()
{
	vector<int> foodTimes = { 3, 1, 2 };
	int k = 5;
	int answer = solution(foodTimes, k);

	return 0;
}

5번

#include <vector>
#include <iostream>
#include <algorithm>

#define MAX_NODES 10001

using namespace std;

struct Node {
	int num;
	int x, y;
	Node* left, * right;
};

Node nodes[MAX_NODES];
int numOfNodes;
Node* root;

void initNodes(vector<pair<int, int>>& nodeinfo)
{
	numOfNodes = nodeinfo.size();

	for (int i = 0; i < numOfNodes; i++) {
		nodes[i].num = i + 1;
		nodes[i].x = nodeinfo[i].first;
		nodes[i].y = nodeinfo[i].second;
		nodes[i].left = NULL;
		nodes[i].right = NULL;
	}
}

bool cmp(Node a, Node b)
{
	return a.x < b.x;
}

void sortNodesByX()
{
	sort(nodes, nodes + numOfNodes, cmp);
}

Node* makeSubTree(Node* arr, int size)
{
	if (size == 0)
		return NULL;

	int maxY = 0;
	int maxYIdx = 0;
	for (int i = 0; i < size; i++) {
		if (arr[i].y > maxY) {
			maxY = arr[i].y;
			maxYIdx = i;
		}
	}

	Node* parent = &arr[maxYIdx];

	parent->left = makeSubTree(arr, maxYIdx);
	parent->right = makeSubTree(arr + maxYIdx + 1, size - maxYIdx -1);

	return parent;
}

void dfs(vector<int>& prePath, vector<int>& postPath, Node* node)
{
	if (node == NULL)
		return;

	prePath.push_back(node->num);
	dfs(prePath, postPath, node->left);
	dfs(prePath, postPath, node->right);
	postPath.push_back(node->num);
}

vector<vector<int>> solution(vector<pair<int, int>>& nodeinfo)
{
	initNodes(nodeinfo);
	sortNodesByX();
	Node *rootNode = makeSubTree(nodes, numOfNodes);

	vector<int> prePath, postPath;
	dfs(prePath, postPath, rootNode);

	return { prePath, postPath };
}

int main()
{
	vector<pair<int, int>> nodeinfo = {
		{5, 3},
		{11, 5},
		{13, 3},
		{3, 5},
		{6, 1},
		{1, 3},
		{8, 6},
		{7, 2},
		{2, 2},
	};

	vector<vector<int>> result = solution(nodeinfo);

	return 0;
}