언제나 처음처럼

[문제 링크]

트라이 자료구조를 사용하여 문자열을 빠르게 검색하는 문제인데 여러가지 고려해줘야할 것이 많아서 어려웠던 문제였다.

먼저 trie 객체에 count 변수를 추가하고 words 문자열이 각 노드를 방문하는 횟수를 카운팅함으로써 해당 위치에서 '?' 를 만났을 경우 가능한 가지수를 탐색하지 않고 바로 반환받을 수 있도록 하였다.

"????o" 와 같이 '?'가 접두사로 등장하는 경우에는 queries를 역순으로 탐색 해줘야하기 때문에 words를 뒤집은 문자열을 가지고 새로운 trie를 한개 더 만들었다.

마지막으로 '?'까지 문자열은 일치하지만 길이가 다른 경우를 걸러주기 위해 trie 객체를 words와 queries의 최대 길이인 10000만큼의 크기를 가진 배열로 선언하여 길이에 따라 다른 트라이에 담아주었다.

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

const int ALPHABETS = 26;

int toNumber(char ch) 
{ 
	if (ch == '?') return ALPHABETS;
	
	return ch - 'a'; 
}

struct TrieNode
{
	TrieNode* children[ALPHABETS];
	int count;
	bool terminal;

	TrieNode() : terminal(false), count(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)
	{
		if (here == key.size()) terminal = true;
		else
		{
			int next = toNumber(key[here]);

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

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

	int find(string& key, int here)
	{
		if (here == key.size()) return this->terminal ? 1 : 0;

		int next = toNumber(key[here]);

		int cnt = 0;

		if (next == ALPHABETS)
		{
			for (int i = 0; i < ALPHABETS; i++)
				if (children[i] != NULL)
					cnt += children[i]->count;
		}
		else
		{
			if (children[next] == NULL) return 0;
			else
			{
				cnt = children[next]->find(key, here + 1);
			}
		}

		return cnt;
	}
};

vector<int> solution(vector<string> words, vector<string> queries) {
	vector<int> answer;

	vector<TrieNode> word(10001);
	vector<TrieNode> reword(10001);

	for (int i = 0; i < words.size(); i++)
	{
		int len = words[i].size();

		word[len].insert(words[i], 0);

		reverse(words[i].begin(), words[i].end());
		
		reword[len].insert(words[i], 0);
	}

	for (int i = 0; i < queries.size(); i++)
	{
		int len = queries[i].size();

		if(queries[i][0] != '?')
			answer.push_back(word[len].find(queries[i], 0));
		else
		{
			reverse(queries[i].begin(), queries[i].end());
			answer.push_back(reword[len].find(queries[i], 0));
		}
	}
	return answer;
}

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

[문제 링크]

입력값이 작음에도 불구하고 완전탐색이 아닌 그리디 알고리즘으로 풀어볼려고 접근하다가 고생만 잔뜩 했다.

그냥 무난하게 모든 경우에 대해서 전부 시도해보면 되는 문제였다.

우선 거리 계산을 편하게 하기 위해 입력으로 주어지는 weak 배열의 각 지점 사이의 거리 차이를 계산해서 weakDist 배열에 저장하였다.

그다음 next_permutation() 함수를 통해 dist 배열로 만들 수 있는 모든 조합에 대해서 외벽 점검을 돌려 가장 최소 인원이 투입되는 경우를 구하면 된다.

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

const int INF = 987654321;

int solution(int n, vector<int> weak, vector<int> dist) {
	int answer = INF;

	vector<int> weakDist;

	for (int i = 0; i < weak.size(); i++)
	{
		if (i == weak.size() - 1)
			weakDist.push_back(n - (weak[i] - weak[0]));
		else
			weakDist.push_back(weak[i + 1] - weak[i]);
	}

	do
	{
		for (int i = 0; i < weakDist.size(); i++)
		{
			int pick = 0, pickDist = dist[0];

			int start = i;
			int end = start != 0 ? start - 1 : weakDist.size() - 1;

			while (start != end)
			{
				if (pickDist >= weakDist[start])
				{
					pickDist -= weakDist[start];
				}
				else
				{
					if (pick + 1 == dist.size()) break;

					pickDist = dist[++pick];
				}

				start = start + 1 == weakDist.size() ? 0 : start + 1;
			}

			if (start != end) pick = INF;

			answer = min(answer, pick + 1);
		}
	} while (next_permutation(dist.begin(), dist.end()));


	return answer == INF ? -1 : answer;
}

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

[문제 링크]

문제 접근에 따라 구현 난이도가 극심하게 달라질 수도 있다는 것을 깨닫게 해준 문제였다.

필자는 크기가 (n+1)X(n+1)인 board 배열을 하나 만든 다음 그 위에다 구조물을 설치하고 제거하는 식으로 구현하려했는데, 이 방법으로 구현할 경우 한 좌표에 기둥과 보가 설치되어 있는 경우를 추가로 고려해줘야하기 때문에 코드도 엄청 길어지고 디버깅하기도 쉽지 않아 한참을 고생했다.

단순하게 2차원 bool 배열을 2개 만들고 기둥이 설치된 정보가 담긴 배열과 보가 설치된 정보가 담긴 배열로 나눠서 관리하면 훨씬 코드도 간결하고 구현도 쉽게 할 수 있었다.

#include <string>
#include <vector>

using namespace std;

bool pillar[101][101];
bool bo[101][101];

bool check_pillar(int y, int x, int n)
{
	if (y == 0) return true;
	if (pillar[y - 1][x]) return true;
	if (x > 0 && bo[y][x - 1]) return true;
	if (bo[y][x]) return true;

	return false;
}

bool check_bo(int y, int x, int n)
{
	if (pillar[y - 1][x]) return true;
	if (x < n && pillar[y - 1][x + 1]) return true;
	if (x > 0 && (bo[y][x-1] && bo[y][x+1])) return true;

	return false;
}

vector<vector<int>> solution(int n, vector<vector<int>> build_frame) 
{	
	for (int i = 0; i < build_frame.size(); i++)
	{
		int xPos = build_frame[i][0];
		int yPos = build_frame[i][1];
		int isStruct = build_frame[i][2];
		int isWork = build_frame[i][3];

		if (isStruct == 0) // 기둥
		{
			if (isWork == 1) // 설치
			{
				if (check_pillar(yPos, xPos, n))
					pillar[yPos][xPos] = true;
			}

			else // 삭제
			{
				pillar[yPos][xPos] = false;

				if (yPos < n && pillar[yPos+1][xPos] && !check_pillar(yPos + 1, xPos, n))
					pillar[yPos][xPos] = true;

				else if (xPos < n && bo[yPos+1][xPos] && !check_bo(yPos + 1, xPos, n))
					pillar[yPos][xPos] = true;

				else if (xPos > 0 && bo[yPos+1][xPos-1] && !check_bo(yPos + 1, xPos - 1, n))
					pillar[yPos][xPos] = true;
			}
		}
		else // 보
		{
			if (isWork == 1) // 설치
			{
				if (check_bo(yPos, xPos, n))
					bo[yPos][xPos] = true;
			}

			else // 삭제
			{
				bo[yPos][xPos] = false;

				if (yPos < n && pillar[yPos][xPos] && !check_pillar(yPos, xPos, n))
					bo[yPos][xPos] = true;

				else if (yPos < n && xPos < n && pillar[yPos][xPos+1] && !check_pillar(yPos, xPos + 1, n))
					bo[yPos][xPos] = true;

				else if (xPos > 0 && bo[yPos][xPos-1] && !check_bo(yPos, xPos - 1, n))
					bo[yPos][xPos] = true;

				else if (xPos < n && bo[yPos][xPos+1] && !check_bo(yPos, xPos + 1, n))
					bo[yPos][xPos] = true;
			}
		}
	}

	vector<vector<int>> answer;
	
	for(int x = 0; x <= n; x++)
		for (int y = 0; y <= n; y++)
		{
			if (pillar[y][x])
				answer.push_back({ x,y,0 });

			if (bo[y][x])
				answer.push_back({ x,y,1 });
		}

	return answer;
}

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

[문제 링크]

스택을 사용하면 쉽게 풀 수 있는 문제였다.

배열 기준으로 move[i] - 1 위치에서 인형을 뽑게 되고, 인형을 찾을 때 까지(배열 원소가 0이 아닌 지점) depth = 0 부터 (board.size()-1) 까지 탐색한다.

인형을 찾으면 탐색을 종료하고 인형을 바구니에 담는다. 이때 바구니의 가장 위에 있는 인형과 동일한 인형이라면 가장 위에 있는 인형을 제거하고 answer 값을 2 증가시킨다.

만약 depth == board.size() 라면 인형을 못찾은 것이므로 건너뛰도록 구현하였다.

#include <string>
#include <stack>
#include <vector>

using namespace std;

int solution(vector<vector<int>> board, vector<int> moves) {
	int answer = 0;
	stack<int> basket;

	for (int i = 0; i < moves.size(); i++)
	{
		int depth = 0;

		while (depth < board.size() && board[depth][moves[i] - 1] == 0)
			depth++;

		if (depth == board.size())
			continue;

		int pick = board[depth][moves[i] - 1];
		
		board[depth][moves[i] - 1] = 0;

		if (!basket.empty() && basket.top() == pick)
		{
			basket.pop();
			answer += 2;
		}
		else
			basket.push(pick);

	}

	return answer;
}

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

[문제 링크]

N과 M의 최대 길이가 20으로 완전탐색을 돌리면 무난히 풀 수 있는 문제였다.

하지만 풀이법을 떠올리기가 정말 어려웠던거 같다.

처음엔 key 배열을 회전시키는 함수와 상하좌우로 한칸씩 밀어내는 함수를 구현해서 풀려고 했는데 조금만 생각해봐도 무수한 반례가 존재하는 풀이였다.

key를 모든 경우에 대조하기 위한 다른사람의 풀이법을 참고하기 위해 찾아보다 좋은 풀이법을 발견하고 바로 구현할 수 있었다.

https://regularmember.tistory.com/186

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

vector<vector<int>> rotate(const vector<vector<int>>& key)
{
	int len = key[0].size();
	vector<vector<int>> ret(len);

	for(int i=0; i<len; i++)
		for (int j = 0; j < len; j++)
			ret[i].push_back(key[len-1-j][i]);

	return ret;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
	int M = key[0].size(), N = lock[0].size();
	int T = N + (M - 1) * 2;
	vector<vector<int>> total(T);
	
	int concave = 0;

	for(int i = 0; i < T; i++)
		for (int j = 0; j < T; j++)
		{
			if ((i >= M - 1 && j >= M - 1) && (i <= T - M && j <= T - M))
			{
				total[i].push_back(lock[i-(M-1)][j-(M-1)]);
				if (lock[i-(M-1)][j-(M-1)] == 0)
					concave++;
			}
			else
				total[i].push_back(2);

		}

	for (int i = 0; i < 4; i++)
	{
		for (int startY = 0; startY <= T - M; startY++)
		{
			for (int startX = 0; startX <= T - M; startX++)
			{
				bool check = true;
				int remain = concave;

				for (int keyY = 0; keyY < M; keyY++)
				{
					for (int keyX = 0; keyX < M; keyX++)
					{
						int keyVal = key[keyY][keyX];
						int totalVal = total[startY + keyY][startX + keyX];

						if (keyVal == totalVal)
						{
							check = false;
							break;
						}
						if (keyVal == 1 && totalVal == 0)
							remain--;
					}
					if (!check) break;
				}
				if (check && remain == 0)
					return true;
			}
		}

		key = rotate(key);
	}

	return false;
}

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

[문제 링크]

스택의 대표적인 문제라고 볼 수 있는 괄호 체크와 분할정복이 섞인 문제였던거 같다.

입력으로 주어지는 문자열 p는 곧 문자열 u = p와 빈 문자열 v가 주어진 형태라고 볼 수 있다.

따라서 문제에서 요구하는 알고리즘대로 구현하면 된다.

먼저 문자열 p가 올바른 괄호 문자열인지 확인해야 한다.

만약 올바른 괄호 문자열이라면 그대로 출력해주면 되고, 올바른 괄호 문자열이 아닐 경우 p를 u와 v로 나눠야 하는데

문제에서 u는 더이상 쪼개질 수 없는 균형잡힌 문자열로 나눠야 한다고 나와있기 때문에 '(' 와 ')' 의 개수가 같아지는 지점을 기준으로 u와 v로 나누면 된다.

마지막으로 나눠진 u에 대해서 올바른 괄호 문자열인지 확인하고, 문제에서 시키는데로 문자열을 완성해주면 된다.

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

bool match(const string& p)
{
	stack<char> temp;

	for (int i = 0; i < p.length(); i++)
	{
		if (p[i] == ')')
		{
			if (temp.empty())
				return false;
			
			temp.pop();
		}
		else
			temp.push(p[i]);
	}
	if (!temp.empty())
		return false;

	return true;
}

string solution(string p) {
	string answer = "";
	
	bool check = match(p);

	if (check)
		return p;
	else
	{
		int uLen;
		stack<char> temp;

		for (uLen = 0; uLen < p.length(); uLen++)
		{
			if (!temp.empty() && temp.top() != p[uLen])
				temp.pop();
			else
				temp.push(p[uLen]);

			if (temp.empty())
				break;
		}
		uLen++;

		string u = p.substr(0, uLen);
		string v = p.substr(uLen);

		check = match(u);

		if (check)
			answer = u + solution(v);
		else
		{
			answer = '(' + solution(v) + ')';
			for (int i = 1; i < uLen - 1; i++)
			{
				if (u[i] == '(')
					answer.push_back(')');
				else
					answer.push_back('(');
			}
		}
	}

	return answer;
}

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

[문제 링크]

문자열의 길이가 최대 1000이므로 모든 경우에 대해 시도해보는 O(N^2) 알고리즘을 구현해도 무난히 통과할 수 있다.

입력받은 문자열을 압축하기 전 길이가 최댓값이기 때문에 answer를 압축하기 전 길이로 초기화해주었다.

그다음 2중 for문을 통해 문자열을 1 ~ (s.length() / 2) 개 단위로 잘랐을 때 만들어지는 압축 문자열 중 길이가 가장 짧은 값을 answer에 갱신해주면 정답을 얻을 수 있다.

#include <string>
#include <vector>

using namespace std;

int solution(string s) {
	int sLen = s.length();
	int answer = sLen;
	
	for (int i = 1; i <= sLen / 2; i++)
	{
		string temp;
		string idx = s.substr(0, i);
		int cnt = 1;
		int here;

		for(here = i; here + i <= sLen; here += i)
		{
			if (idx == s.substr(here, i))
				cnt++;
			else
			{
				if (cnt > 1)
					temp += to_string(cnt) + idx;
				else
					temp += idx;

				idx = s.substr(here, i);
				cnt = 1;
			}
		}

		if (cnt > 1)
			temp += to_string(cnt) + idx;
		else
			temp += idx;

		temp += s.substr(here);

		answer = answer < temp.length() ? answer : temp.length();
	}

	return answer;
}

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

[문제 링크]

제약사항이 많은 문제였는데, 양질의 문제는 아니였던거같다.

전체적인 알고리즘은 다음과 같다.

입력받은 vector<string>의 원소를 key 값으로 받는 map<string, int> 컨테이너를 만든 다음 key값과 일치하는 재생횟수를 누적시키고,

마찬가지로 vector<string> 배열의 원소를 key 값으로 받는 map<string, vector<pair<int, int>>> 컨테이너를 만든 다음 key값과 일치하는 재생횟수와, 고유 번호를 pair 쌍으로 저장하여 vector 컨테이너에 쌓는다. 

이 과정을 통해 각 장르별 총 재생 횟수와 장르별 고유 번호와 재생 횟수를 파악할 수 있게 된다.

그다음 많이 재생된 장르 순으로 오름차순 정렬하고, 장르별 재생 횟수가 많은 고유번호 순으로 정렬을 수행한다.

추가로 문제의 요구사항에 맞춰 재생 횟수가 일치하는 경우 고유번호가 작은 것이 앞에 오도록 처리해주자.

마지막으로 가장 많이 재생된 장르순으로 그 장르에서 재생 횟수가 많은 고유번호를 2개 뽑아 answer에 담아주면 된다.

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

using namespace std;

bool compare(const pair<int, int> left, const pair<int, int> right)
{
	if (left.first == right.first)
		return left.second < right.second;
	else
		return left.first > right.first;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
	vector<int> answer;
	map<string, int> playsCnt;
	map<string, vector<pair<int, int>>> genresBest;

	for (int i = 0; i < genres.size(); i++)
	{
		playsCnt[genres[i]] += plays[i];
		genresBest[genres[i]].push_back(make_pair(plays[i], i));
	}

	map<string, int>::iterator iter = playsCnt.begin();
	vector<pair<int, string>> sortPlays;

	while (iter != playsCnt.end())
	{
		sortPlays.push_back({ iter->second, iter->first });
		iter++;
	}

	sort(sortPlays.begin(), sortPlays.end(), greater<pair<int, string>>());

	for (int i = 0; i < sortPlays.size(); i++)
	{
		string pick = sortPlays[i].second;
		vector<pair<int, int>> temp = genresBest[pick];

		sort(temp.begin(), temp.end(), compare);

		for (int j = 0; j < temp.size(); j++)
		{
			if (j == 2) break;
			answer.push_back(temp[j].second);
		}

		temp.clear();
	}

	return answer;
}

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