Feel Coding

https://www.acmicpc.net/problem/1759

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

int r, n;
vector<char> v;

void select(vector<bool> visited, vector<char> result, int num) {
	if (num == r) {
		int vowelCount = 0;
		int consonantCount = 0;	
		for (int i = 0; i < r; i++) {
			if (result[i] == 'a' || result[i] == 'e' || result[i] == 'i' || result[i] == 'o' || result[i] == 'u') 
				vowelCount++;
			else 
				consonantCount++;
		}
		if (!(vowelCount >= 1 && consonantCount >= 2)) {
			return;
		}
		for (int i = 0; i < r; i++) {
			cout << result[i];
		}
		cout << '\n';
		return;
	}
	for (int i = 0; i < n; i++) {
		if (!visited[i]) {
			if (num == 0) {
				visited[i] = true;
				result[num] = v[i];
				select(visited, result, num + 1);
				visited[i] = false;
			}
			else {
				if (result[num - 1] < v[i]) {
					visited[i] = true;
					result[num] = v[i];
					select(visited, result, num + 1);
					visited[i] = false;
				}
			}
		}
	}
}

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	cin >> r >> n;
	for (int i = 0; i < n; i++) {
		char temp;
		cin >> temp;
		v.push_back(temp);
	}
	sort(v.begin(), v.end());
	vector<char> result(r);
	vector<bool> visited(n);
	select(visited, result, 0);
	return 0;
}

https://www.acmicpc.net/problem/4641

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

int main() {
	while (true) {
		int first;
		cin >> first;
		if (first == -1) break;
		vector<int> v;
		v.push_back(first);
		while (true) {
			int n;
			cin >> n;
			if (n == 0) break;
			v.push_back(n);

		}
		int count = 0;
		for (int i = 0; i < v.size(); i++) {
			for (int j = 0; j < v.size(); j++) {
				if (v[j] == v[i] * 2) count++;
			}
		}
		cout << count << '\n';
	}
	return 0;
}

https://www.acmicpc.net/problem/6321

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


int main() {
	int n;
	cin >> n;
	for (int t = 0; t < n; t++) {
		string s;
		cin >> s;
		cout << "String #" << t + 1 << '\n';
		for (int i = 0; i < s.size(); i++) {
			if (s[i] != 90) cout << (char)(s[i] + 1);
			else cout << 'A';
		}
		cout << "\n\n";
	}
	return 0;
}

'\n'을 두 번 쓸 때에는 "\n\n"이라고 쓰는 거 주의하자. 한 줄만 띄는 게 습관이 되어서 자꾸 '\n\n' 한다. 문제는 그렇게 해도 오류가 안 난다. 'hi'이렇게 알파벳은 컴파일 에러가 나는데 \n은 안 난다.

https://www.acmicpc.net/problem/6378

처음에는 이렇게 제출했었는데 틀렸다.

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


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	while (true) {
		int n;
		cin >> n;
		if (n == 0) break;
		while (true) {
			vector<int> v;
			while (n != 0) {
				v.push_back(n % 10);
				n /= 10;
			}
			int total = 0;
			for (int i : v) {
				total += i;
			}
			if (total < 10) {
				cout << total << '\n';
				break;
			}
			else {
				n = total;
			}
		}
	}
	return 0;
}

보니까 숫자는 최대 1000자리수라고 했다.

그러니 당연히 아무리 범위가 큰 타입을 써도 오버플로우가 날 수밖에 없었다.

따라서 문자열로 받아서 풀었다.

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


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int numbers[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	char charNumbers[10] = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' };
	string stringNumbers[10] = { "0", "1", "2", "3", "4", "5", "6", "7", "8", "9" };
	map<char, int> m;
	map<int, string> sm;
	for (int i = 0; i < 10; i++) {
		m[charNumbers[i]] = numbers[i];
		sm[numbers[i]] = stringNumbers[i];
	}
	while (true) {
		string n;
		cin >> n;
		if (n == "0") break;
		while (true) {
			int total = 0;
			for (int i = 0; i < n.size(); i++) {
				total += m[n[i]];
			}
			if (total < 10) {
				cout << total << '\n';
				break;
			}
			else {
				n = "";
				while (total != 0) {
					n.append(sm[total % 10]);
					total /= 10;
				}
			}
		}
	}
	return 0;
}

https://www.acmicpc.net/problem/6679

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


int main() {
	ios_base::sync_with_stdio(false);
	for (int i = 1000; i < 10000; i++) {
		vector<int> binary;
		vector<int> hexadecimal;
		vector<int> decimal;
		int n = i;
		while (n != 0) {
			binary.push_back(n % 12);
			n /= 12;
		}
		n = i;
		while (n != 0) {
			int a = n % 16;
			hexadecimal.push_back(a);
			n /= 16;
		}
		n = i;
		while (n != 0) {
			decimal.push_back(n % 10);
			n /= 10;
		}
		int hexadecimalSum = 0;
		int decimalSum = 0;
		int binarySum = 0;
		for (int num : decimal)
			decimalSum += num;
		for (int num : hexadecimal) {
			hexadecimalSum += num;
		}
		for (int num : binary)
			binarySum += num;
		if (binarySum == decimalSum && decimalSum == hexadecimalSum)
			cout << i << '\n';
	}
	return 0;
}

정말 오늘따라 더 느끼는 문제 똑바로 읽기의 중요성.

2진수인줄 알고 2진수, 10진수 16진수로 했는데 답이 안 나와서 이걸가지고 한 시간을 헤맸다. 그런데 12진수였다.

문제를 똑바로 읽자

https://www.acmicpc.net/problem/2845

#include <iostream>
using namespace std;


int main() {
	int l, p;
	cin >> l >> p;
	for (int i = 0; i < 5; i++) {
		int a;
		cin >> a;
		cout << a - p * l << " ";
	}
	return 0;
}

오늘 다시 한 번 느낀 것. 문제를 똑바로 읽자. l이 기사의 개수인 줄 알고 for문을 i =0부터 i < l까지 돌려서 틀렸었다.

https://www.acmicpc.net/problem/9012

괄호가 맞는지 아닌지는 스택을 사용하여 알아볼 수 있다.

#include <iostream>
#include <stack>
#include <string>
using namespace std;


int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int testCase;
	cin >> testCase;
	for (int t = 0; t < testCase; t++) {
		string s;
		stack<char> stack;
		cin >> s;
		bool flag = false;
		for (int i = 0; i < s.size(); i++) {
			if (s[i] == '(') {
				stack.push('(');
			}
			else {
				if (!stack.empty()) {
					char c = stack.top();
					stack.pop();
					if (c != '(') { //짝이 안 맞으면 NO
						cout << "NO" << '\n';
						flag = true;
						break;
					}
				}
				else {
					cout << "NO" << '\n'; //아직 끝까지 안 봤는데 벌써 스택이 비어있으면 NO
					flag = true;
					break;
				}
			}
		}
		if(!flag && !stack.empty()) cout << "NO" << '\n';
		else if (!flag && stack.empty()) cout << "YES" << '\n';
	}
	return 0;
}

https://www.acmicpc.net/problem/2252

처음에는 이렇게 제출했는데 시간초과가 났다.

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


int main() {
	int n, m;
	cin >> n >> m;
	vector<int> student[32001];
	for (int i = 0; i < m; i++) {
		int shorter, taller;
		cin >> shorter>> taller;
		student[taller].push_back(shorter);
	}
	vector<int> result;

	while(result.size() < n) {
		for (int i = 1; i <= n; i++) {
			if (student[i].size() == 0 && result.size() < n) {
				result.push_back(i);
				for (int j = 1; j <= n; j++) {
					for (int k = 0; k < student[j].size(); k++) {
						if (student[j][k] == i) student[j].erase(student[j].begin() + k);
					}
				}
			}
		}
	}
	for (int i = 0; i < result.size(); i++) {
		cout << result[i] << " ";
	}
	return 0;
}

딱 봐도 시간초과가 날 것인게, while문 안에 3중 for문을 썼다. 반복문을 4개를 중첩해서 쓰니까 당연히 그럴 수밖에 없다.

그래서 다시 풀었다. 

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


int main() {
	int n, m;
	cin >> n >> m;
	vector<int> student[32001];
	vector<int> inDegree(n + 1);
	for (int i = 0; i < m; i++) {
		int shorter, taller;
		cin >> shorter>> taller;
		student[shorter].push_back(taller);
		inDegree[taller]++;
	}
	queue<int> q;
	for (int i = 1; i <= n; i++) {
		if (inDegree[i] == 0) q.push(i);
	}
	while(!q.empty()) {
		int cur = q.front();
		q.pop();
		cout << cur << " ";
		for (int i = 0; i < student[cur].size(); i++) {
			inDegree[student[cur][i]]--;
			if (inDegree[student[cur][i]] == 0) q.push(student[cur][i]);
		}
	}
	return 0;
}

역시 알고리즘은 정석대로 자료구조 책에 있는 방법대로 해야 하나보다. 그래도 자료구조 수업에서 위상정렬을 배운지 거의 6개월이 넘었는데 방법을 잊지 않고 스스로 구현했다는 것이 대단하다.

https://www.acmicpc.net/problem/2161

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


int main() {
	queue<int> q;
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		q.push(i);
	}
	while (true) {
		if (q.size() == 1) break;
		int discard = q.front();
		q.pop();
		cout << discard << " ";
		if (q.size() == 1) break;
		int cur = q.front();
		q.pop();
		q.push(cur);
	}
	cout << q.front();
	return 0;
}

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


int main() {
	string a, b;
	cin >> a >> b;
	int minCount = 0;
	if (a.size() == b.size()) {
		for (int i = 0; i < a.size(); i++) {
			if (a[i] != b[i]) minCount++;
		}
	}

	else {
		int difference = b.size() - a.size();
		minCount = 51;
		for (int i = 0; i <= difference; i++) {
			int count = 0;
			for (int j = i; j < i + a.size(); j++) {
				if (a[j - i] != b[j]) count++;
			}
			if (count < minCount) minCount = count;
		}
	}
	cout << minCount;
	return 0;
}