99코딩

문제

풀이

 모든 땅의 높이가 각각 0,1,2,...,254,255,256으로 맞춰지는 시간을 구하여 그 중 최소 시간과 최소 시간이 나올 때의 땅의 높이를 구해 출력하면 된다.

#include <iostream>
#include <vector>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m, b;
	int board[501][501];
	int minTime = 0x7f7f7f7f;
	int maxH = -1;

	cin >> n >> m >> b;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> board[i][j];

	for (int height = 0; height <= 256; height++) {
		int removeBlock = 0, deployBlock = 0;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				int h = board[i][j] - height;
				if (h > 0) removeBlock += h;
				else if (h < 0) deployBlock -= h;
			}
		}

		if (removeBlock + b >= deployBlock) {
			int t = 2 * removeBlock + deployBlock;
			if (t <= minTime) {
				minTime = t;
				maxH = height;
			}
		}
	}

	cout << minTime << " " << maxH;

	return 0;
}

문제

풀이

스택 자료구조를 활용하면 간단하게 해결할 수 있는 문제다.

#include <iostream>
#include <stack>

using namespace std;

int main() {
	int n, num; 
	int sum = 0;
	stack<int> s;

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> num;

		if (num == 0) s.pop();
		else s.push(num);
	}
	
	while (s.size() > 0) {
		sum += s.top();
		s.pop();
	}

	cout << sum;

	return 0;
}

문제

풀이

 문자열을 받아 여는 괄호일 때 cnt를 증가 시키고, 닫는 괄호는 cnt를 감소시킨다. 이후 cnt가 0보다 작다면 flag를 false로 바꾸고 break한다. 반복문이 끝난 후 flag가 false거나 cnt가 0이 아니라면 NO를 출력, 조건을 만족하면 YES를 출력한다.

#include <iostream>
#include <string>

using namespace std;

int main() {
	int n;
	string str;

	cin >> n;

	for (int i = 0; i < n; i++) {
		int cnt = 0;
		bool isVPS = true;

		cin >> str;

		for (int i = 0; i < str.size(); i++) {
			if (str[i] == '(') cnt++;
			else if (str[i] == ')') cnt--;

			if (cnt < 0) {
				isVPS = false;
				break;
			}
		}

		if (isVPS == false || cnt != 0) cout << "NO\n";
		else cout << "YES\n";
	}

	return 0;
}

문제

풀이

 문자열을 받아 여는 괄호는 스택에 담고, 닫는 괄호는 스택이 비어있지 않고, 스택의 탑이 해당 닫는 괄호와 매칭이 되는 여는 괄호인지 체크해서 두 조건을 만족하면 pop() 만족하지 않으면 flag를 false로 바꾸고 break 한다.

 이후 스택이 비어있고, flag가 true면 균형잡힌 문자열이므로 yes 출력, 아니라면 no를 출력하도록 한다.

#include <iostream>
#include <string>
#include <stack>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 
	cout.tie(NULL);

	while (true) {
		bool flag = true;
		string s;
		stack<char> bracket;

		getline(cin, s);
		
		if (s == ".") break;

		for (int i = 0; i < s.length(); i++) {
			char c = s[i];

			if (c == '(' || c == '[')
				bracket.push(c);
			else if (c == ')') {
				if (!bracket.empty() && bracket.top() == '(')
					bracket.pop();
				else {
					flag = false;
					break;
				}
					
			}
			else if (c == ']') {
				if (!bracket.empty() && bracket.top() == '[')
					bracket.pop();
				else {
					flag = false;
					break;
				}
			}
		}

		if (bracket.empty() && flag == true) cout << "yes\n";
		else cout << "no\n";
	}
    
	return 0;
}

문제

풀이

선입선출(FIFO: First-In First-Out)의 구조를 가지는 큐(Queue)를 이용하면 간단하게 해결할 수 있는 문제다.

#include <iostream>
#include <queue>

using namespace std;

int main() {
	int n;
	queue<int> q;

	cin >> n;

	for (int i = 1; i <= n; i++)
		q.push(i);

	while (q.size() > 1) {
		q.pop();
		q.push(q.front());
		q.pop();
	}

	cout << q.front();

	return 0;
}

문제

풀이

선형탐색(Linear Search)을 이용하면 시간초과가 발생하기 때문에 이분탐색(Binary Search)을 통해 해결하였습니다.

#include <iostream>
#include <algorithm>

using namespace std;

int arr[100001];

void binary_search(int list[], int key, int right) {
	int left = 0;
	int middle;

	while (left <= right) {
		middle = (left + right) / 2;

		if (key == list[middle]) {
			cout << "1\n";
			return;
			}
		else if (key > list[middle])
			left = middle + 1;
		else if (key < list[middle])
			right = middle - 1;
	}

	cout << "0\n";
	return;
}

int main() {
	int n, m, num;

	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> arr[i];
		
	sort(arr, arr + n);

	cin >> m;

	for (int i = 0; i < m; i++) {
		cin >> num;

		binary_search(arr, num, n - 1);
	}

	return 0;
}

문제

풀이

 특정 집단에서 k번째 인원을 아무도 남지 않을 때까지 반복해서 제거하고 이 제거되는 순서대로 해당 인원의 번호를 출력하면 된다. 이 문제는 큐를 통해 쉽게 해결할 수 있다.

#include <iostream>
#include <queue>

using namespace std;

int main() {
	int n, k;
	queue<int> q;

	cin >> n >> k;

	for (int i = 1; i <= n; i++)
		q.push(i);

	cout << "<";

	while (q.size() > 0) {
		for (int i = 0; i < k - 1; i++) {
			q.push(q.front());
			q.pop();
		}

		if (q.size() > 1) cout << q.front() << ", ";
		else cout << q.front() << ">";
		q.pop();
	}

	return 0;
}

문제

풀이

키와 몸무게를 한 쌍으로 배열에 받은 뒤, 각 인원별로 키와 몸무게 둘 다 해당 인원보다 큰 사람의 수를 세면 된다.

#include <iostream>
#include <vector>

using namespace std;

int main() {
	int n;
	vector<pair<int, int>> v;

	cin >> n;

	for (int i = 0; i < n; i++) {
		int weight, height;

		cin >> weight >> height;
		v.push_back({ weight, height });
	}

	for (int i = 0; i < n; i++) {
		int cnt = 0;

		for (int j = 0; j < n; j++) {
			if (i == j) cnt++;
			if ((v[i].first < v[j].first) && (v[i].second < v[j].second)) cnt++;
		}

		cout << cnt << " ";
	}

	return 0;
}