언제나 처음처럼

[문제 링크]

이 문제와 같이 많은 양의 문자열을 검색하는 요구하는 문제들은 트라이 자료구조를 활용하면 효율적으로 해결할 수 있다.

트라이 자료구조는 알고리즘 문제해결 전략에서 구현한 것과 똑같이 구현하였다.

사전에 포함된 단어들을 출현 빈도에 따라 내림차순으로 정렬하고 출현 빈도가 같을 경우 오름차순으로 정렬하기 위해 출현 빈도 freq에 -를 붙여서 배열에 담았다.

스페이스바를 누르는 횟수까지 포함시켜야 하므로 cnt를 M - 1 로 초기화 하였다.

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

const int ALPHABETS = 26;

int toNumber(char ch) 
{ 
	return ch - 'A'; 
}

struct TrieNode
{
	TrieNode* children[ALPHABETS];
	int first;
	int terminal;

	TrieNode() : terminal(-1), first(-1)
	{
		memset(children, 0, sizeof(children));
	}
	~TrieNode()
	{
		for (int i = 0; i < ALPHABETS; i++)
			if (children[i]) delete children[i];
	}

	void insert(string& key, int here, int id)
	{
		if (first == -1) 
			first = id;

		if (here == key.size())
			terminal = id;
		else
		{
			int next = toNumber(key[here]);

			//자식 노드가 없다면 생성
			if (children[next] == NULL)
				children[next] = new TrieNode();

			children[next]->insert(key, here + 1, id);
		}
	}

	int type(string& key, int here, int id)
	{
		if (here == key.size()) return 0;

		if (first == id) return 1;

		int next = toNumber(key[here]);

		return 1 + children[next]->type(key, here + 1, id);
	}

	TrieNode* find(string& key, int here)
	{
		if (here == key.size()) return this;
		
		int next = toNumber(key[here]);

		if (children[next] == NULL) return NULL;
		return children[next]->find(key, here + 1);
	}
};

int countKeys(TrieNode& trie, string word)
{
	TrieNode* node = trie.find(word, 0);

	if (node == NULL || node->terminal == -1)
		return word.size();

	return trie.type(word, 0, node->terminal);
}

int main(void)
{
	cin.tie(0);
	ios_base::sync_with_stdio(0);

	int tc;
	cin >> tc;

	while (tc--)
	{
		int N, M;
		cin >> N >> M;

		
		vector<pair<int, string>> input;

		for (int i = 0; i < N; i++)
		{
			string words;
			int freq;
			cin >> words >> freq;
			input.push_back({ -freq, words });
		}

		sort(input.begin(), input.end());

		TrieNode word;
		
		for(int i=0; i<input.size(); i++)
			word.insert(input[i].second, 0, i);
		
		word.first = -1;

		int cnt = M - 1;

		for (int i = 0; i < M; i++)
		{
			string words;
			cin >> words;

			cnt += countKeys(word, words);
		}

		cout << cnt << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 144 day

[문제 링크]

세그먼트 트리라고 불리는 구간 트리를 활용하면 쉽게 풀 수 있는 문제였다.

구간의 최솟값을 저장하는 구간 트리는 알고리즘 문제해결 전략에 나와있는대로 구현하였고 구간의 최댓값을 구하기 위해 배열에 -1을 곱한 뒤 구간 트리를 한개 더 만들었다.

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

const int INTMAX = numeric_limits<int>::max();

void getMinus(int& a)
{
	a *= -1;
}

class RMQ {
	int n;
	vector<int> rangeMin;

	int init(const vector<int>& array, int left, int right, int node)
	{
		if (left == right)
			return rangeMin[node] = array[left];
		int mid = (left + right) / 2;
		int leftMin = init(array, left, mid, node * 2);
		int rightMin = init(array, mid + 1, right, node * 2 + 1);

		return rangeMin[node] = min(leftMin, rightMin);
	}

	int query(int left, int right, int node, int nodeLeft, int nodeRight)
	{
		if (right < nodeLeft || nodeRight < left) return INTMAX;
		if (left <= nodeLeft && nodeRight <= right) return rangeMin[node];

		int mid = (nodeLeft + nodeRight) / 2;
		return min(query(left, right, node * 2, nodeLeft, mid),
			query(left, right, node * 2 + 1, mid + 1, nodeRight));
	}

	int update(int index, int newValue, int node, int nodeLeft, int nodeRight)
	{
		if (index < nodeLeft || nodeRight < index) return rangeMin[node];
		if (nodeLeft == nodeRight) return rangeMin[node] = newValue;

		int mid = (nodeLeft + nodeRight) / 2;
		
		return rangeMin[node] = min(update(index, newValue, node * 2, nodeLeft, mid),
			update(index, newValue, node * 2 + 1, mid + 1, nodeRight));
	}

public:
	RMQ(const vector<int>& array)
	{
		n = array.size();
		rangeMin.resize(n * 4);
		init(array, 0, n - 1, 1);
	}

	int query(int left, int right)
	{
		return query(left, right, 1, 0, n - 1);
	}

	int update(int index, int newValue)
	{
		return update(index, newValue, 1, 0, n - 1);
	}
};

int main(void)
{
	cin.tie(0);
	ios_base::sync_with_stdio(0);

	int tc;
	cin >> tc;

	while (tc--)
	{
		int N, Q;
		cin >> N >> Q;

		vector<int> board(N);
		for (int i = 0; i < N; i++)
			cin >> board[i];

		RMQ boardMin(board);

		for_each(board.begin(), board.end(), getMinus);

		RMQ boardMax(board);

		for (int i = 0; i < Q; i++)
		{
			int first, last;
			cin >> first >> last;


			cout << -boardMax.query(first, last) - boardMin.query(first, last) << endl;
		}
	}
}

알고리즘 200일 프로젝트 - 143 day

[문제 링크]

알고리즘 문제해결 전략의 이진검색 트리를 공부하면서 풀게된 문제였다.

예전에 풀었던 백준: 신입사원 문제 와 거의 같은 유형의 문제라고 생각한다.

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

bool isDominated(map<int, int>& data, int p, int q)
{
	map<int, int>::iterator iter = data.lower_bound(p);

	if (iter == data.end()) return false;

	return iter->second > q;
}

void removeDominated(map<int, int>& data, int p, int q)
{
	map<int, int>::iterator iter = data.lower_bound(p);

	if (iter == data.begin()) return;
	iter--;

	while (1)
	{
		if (iter->second > q) return;

		if (iter == data.begin())
		{
			data.erase(iter); 
			break;
		}
		else
		{
			map<int, int>::iterator temp = iter;
			temp--;
			data.erase(iter);
			iter = temp;
		}
	}
}

int main(void)
{
	cin.tie(0);
	ios_base::sync_with_stdio(0);

	int tc;
	cin >> tc;

	while (tc--)
	{
		int N;
		cin >> N;

		int cnt = 0;
		map<int, int> coords;

		for (int i = 0; i < N; i++)
		{
			int p, q;
			cin >> p >> q;

			if (isDominated(coords, p, q))
				cnt += coords.size();
			else
			{
				removeDominated(coords, p, q);
				coords[p] = q;
				cnt += coords.size();
			}
		}

		cout << cnt << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 142 day

[문제 링크]

KMP 알고리즘이 활용되는 문제가 정말 많은거 같다.

금고를 반시계방향으로 돌려서 맞추는 횟수는 shifts(a, b) 함수의 반환값을 통해 알 수 있다.

돌리기 전 문자열을 a, 반시계 방향으로 돌리고 난 후 문자열을 b라고 했을 때 shifts(a, b) 를 수행하면 a문자열과 같은 문자열을 뒤에 붙인 문자열이 만들어지는데 이 문자열에서 b의 위치를 KMP 알고리즘을 통해 빠르게 구할 수 있다.

이 때 구한 b의 위치가 곧 돌린 횟수가 되므로 결과값에 누적시킨다.

문제를 해결하기 위해선 반시계방향, 시계방향으로 번갈아가며 돌려야 한다.

a문자열을 시계방향으로 돌려서 b문자열을 만드는데 돌리는 횟수와 b문자열을 반시계방향으로 돌려서 a문자열을 만드는 횟수가 같기 때문에 이를 이용하여 매개변수의 순서를 바꾼 shifts(b, a) 를 수행하면 동일한 결과를 얻을 수 있다.

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

vector<int> getPartialMatch(const string& s)
{
	int len = s.size();
	vector<int> pi(len, 0);

	int begin = 1, matched = 0;
	while (begin + matched < len)
	{
		if (s[begin + matched] == s[matched])
		{
			matched++;
			pi[begin + matched - 1] = matched;
		}
		else
		{
			if (matched == 0)
				begin++;
			else
			{
				begin += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}

	return pi;
}

int KMPsearch(const string& h, const string& s)
{
	int hLen = h.size(), sLen = s.size();
	int ret;
	vector<int> pi = getPartialMatch(s);

	int begin = 0, matched = 0;
	while (begin <= hLen - sLen)
	{
		if (matched < sLen && h[begin + matched] == s[matched])
		{
			matched++;

			if (matched == sLen)
			{
				ret = begin;
				break;
			}
		}
		else
		{
			if (matched == 0)
				begin++;
			else
			{
				begin += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}

	return ret;
}

int shifts(const string& original, const string& target)
{
	return KMPsearch(original + original, target);
}

int main(void)
{
	int tc;
	cin >> tc;

	while (tc--)
	{
		int N;
		cin >> N;

		vector<string> s(N+1);
		for (int i = 0; i <= N; i++)
			cin >> s[i];

		int sum = 0;
		for (int i = 0; i < N; i++)
		{
			if (i % 2 != 0)
				sum += shifts(s[i], s[i + 1]);
			else
				sum += shifts(s[i + 1], s[i]);
		}

		cout << sum << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 138 day

[문제 링크]

KMP 알고리즘을 알기 전에는 팰린드롬 만들기 문제를 엄청 비효율적으로 풀었던거 같은데, KMP알고리즘을 배우면서 부분문자열의 접두사와 접미사가 일치하는 최대 길이를 효율적으로 구할 수 있게 되었다.

문자열 S와 이를 뒤집은 'S 문자열을 가지고 S의 접미사이면서 'S의 접두사가 되는 구간의 최대 길이를 찾은 다음, 문자열 S의 시작부분 부터 접미사가 시작되는 부분 전까지의 길이를 S 뒤에 붙여주면 가장 짧은 팰린드롬이 완성된다.

완성한 팰린드롬의 길이를 출력하면 원하는 결과를 얻을 수 있다.

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

vector<int> getPartialMatch(string& rS)
{
	int len = rS.size();
	vector<int> pi(len, 0);

	int begin = 1, matched = 0;
	while (begin + matched < len)
	{
		if (rS[begin + matched] == rS[matched])
		{
			matched++;
			pi[begin + matched - 1] = matched;
		}
		else
		{
			if (matched == 0)
				begin++;
			else
			{
				begin += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}

	return pi;
}

int KMPsearch(string& S)
{
	int len = S.size();
	string rS;

	for (int i = len - 1; i >= 0; i--)
		rS.push_back(S[i]);
	
	vector<int> pi = getPartialMatch(rS);

	int begin = 0, matched = 0, addLen = len;
	while (begin + matched < len)
	{
		if (matched < len && S[begin + matched] == rS[matched])
		{
			matched++;
			
			if (matched == len - begin)
			{
				addLen = begin;
				break;
			}
		}
		else
		{
			if (matched == 0)
				begin++;
			else
			{
				begin += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}

	return len + addLen;
}

int main(void)
{
	int tc;
	cin >> tc;
	
	while (tc--)
	{
		string S;
		cin >> S;
		cout << KMPsearch(S) << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 138 day

[문제 링크]

알고리즘 문제해결 전략 책에 있는 예제인데 투포인터를 응용한 재미있는 문제였다.

메모리 제한이 64MB 이하이므로 최대 50,000,000인 N을 배열에 담을 수 없다.

따라서 외계 신호를 받을때마다 구간합에 누적하고 결과값을 갱신해야 한다. 그리고 큐에 누적시킨 외계 신호를 보관하고 있다가 구간합이 K보다 커지게 되면 구간합이 K보다 같거나 작아질 때까지 먼저 들어온 순서대로 빼준다.

구간합이 K와 같다면 신호와 일치한 것이므로 결과값을 1 증가시킨다.

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

const long long MOD = pow(2, 32);

class Signal
{
	long long num;

public:
	Signal() : num(1983) {}
	int next()
	{
		long long ret = num;
		
		num = (num * 214013 + 2531011) % MOD;
		
		return ret % 10000 + 1;
	}
};

int main(void)
{
	int tc;
	cin >> tc;

	while (tc--)
	{
		int K, N;
		cin >> K >> N;

		Signal signal;
		queue<int> range;
		int ret = 0, rangeSum = 0;

		for (int i = 0; i < N; i++)
		{
			int nextSignal = signal.next();
			rangeSum += nextSignal;
			range.push(nextSignal);

			while (rangeSum > K)
			{
				rangeSum -= range.front();
				range.pop();
			}

			if (rangeSum == K)
				ret++;
		}

		cout << ret << endl;
	}
	return 0;
}

알고리즘 200일 프로젝트 - 136 day

[문제 링크]

스택을 이용하여 풀 수 있는 간단한 문제였다.

여는 괄호는 바로 스택에 쌓고, 닫는 괄호의 경우 스택의 top()에 해당 괄호를 여는 괄호가 있는지 확인하여 있다면 여는 괄호를 스택에서 pop() 해주고, 없다면 잘못된 괄호이므로 "NO"를 반환해준다.

마지막으로 입력받은 괄호 문자열의 끝까지 탐색했다면 스택이 비어있는지 확인 후 비었을 경우 "YES", 비어있지 않을 경우 "NO"를 반환하도록 구현하였다.

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

string Solution(string str)
{
	stack<char> stk;
	for (int i = 0; i < str.size(); i++)
	{
		switch (str[i])
		{
		case ')':
			if (stk.empty() || stk.top() != '(')
				return "NO";
			stk.pop();
			break;

		case '}':
			if (stk.empty() || stk.top() != '{')
				return "NO";
			stk.pop();
			break;

		case ']':
			if (stk.empty() || stk.top() != '[')
				return "NO";
			stk.pop();
			break;

		default:
			stk.push(str[i]);
		}
	}

	return stk.empty() ? "YES" : "NO";
}

int main(void)
{
	int tc;
	cin >> tc;

	while (tc--)
	{
		string str;
		cin >> str;

		cout << Solution(str) << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 136 day

[문제 링크]

연결 리스트인 list 컨테이너를 활용하여 풀 수 있는 간단한 문제였다.

erase() 함수를 수행하면 다음 원소의 반복자를 반환하므로, erase() 후 K-1 만큼 반복자를 이동시킨 다음 반복자가 가리키는 원소를 erase() 하여 최종적으로 2명이 남게되면 결과를 출력하도록 구현하였다.

추가적으로 반복자가 list 의 끝에 도달했을 때 ++ 연산으로 첫번째 원소를 가리킬 수 없으므로, begin()을 통해 list의 첫번째 원소를 가리키도록 해주었다.

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

int main(void)
{
	int tc;
	cin >> tc;

	while (tc--)
	{
		int N, K;
		cin >> N >> K;

		list<int> soldier;
		for (int i = 1; i <= N; i++)
			soldier.push_back(i);

		list<int>::iterator iter = soldier.begin();

		iter = soldier.erase(iter);

		while (soldier.size() > 2)
		{
			for (int i = 1; i < K; i++)
			{
				iter++;
				
				if (iter == soldier.end())
					iter = soldier.begin();
			}

			iter = soldier.erase(iter);

			if (iter == soldier.end())
				iter = soldier.begin();
		}

		cout << soldier.front() << ' ' << soldier.back() << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 136 day