굳건하게

문제 : https://programmers.co.kr/learn/courses/30/lessons/60061

2020 카카오 BLINE RECRUITMENT 기둥과 보 설치

구현 시뮬레이션

 문제에 맞춰서 구현을 하는 문제입니다. 음... 저는 규칙을 잘못이해해서 문제를 푸는데 애를 먹었습니다.

[규칙]

● 기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 합니다.

● 보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다.

기둥과 보의 설치 가능한 조건을 다음과 같습니다. 저는 '보의 한쪽 끝 부분 위에 있거나' , '한쪽 끝 부분이 기둥 위에 있거나' 라는 규칙을 하나의 보 혹은 하나의 기둥의 한쪽 끝 부분 위에 있어야된다! 로 해석해서 다음과 같은 경우가 안된다고 생각했고, WA의 지옥에 빠졌습니다,,,,,,

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

using namespace std;

bool row[102][102], col[102][102];

bool isBuildRow(int x, int y) {
	return col[x][y - 1] || col[x + 1][y - 1] || (row[x - 1][y] && row[x + 1][y]);
}

bool isBuildCol(int x, int y) {
	return y == 1 || col[x][y - 1] || row[x - 1][y] || row[x][y];
}

bool isRemove(int n) {
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			if (row[i][j] && !isBuildRow(i, j))
				return false;
			if (col[i][j] && !isBuildCol( i, j))
				return false;
		}
	return true;
}

vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
	for (int i = 1; i <= 101; i++)
		for (int j = 1; j <= 101; j++)
			row[i][j] = col[i][j] = 0;

	for (int i = 0; i < build_frame.size(); i++) {
		int x = build_frame[i][0], y = build_frame[i][1], a = build_frame[i][2], b = build_frame[i][3];
		x++, y++;
		if (b == 0) { // 삭제
			if (a == 0) { // 기둥
				col[x][y] = 0;
				if (isRemove(n + 1))
					continue;
				col[x][y] = 1;
			}
			else {
				row[x][y] = 0;
				if (isRemove(n + 1))
					continue;
				row[x][y] = 1;
			}
		}
		else { // 설치
			if (a == 0) { // 기둥
				if (isBuildCol( x, y))
					col[x][y] = 1;
			}
			else { // 보
				if (isBuildRow( x, y))
					row[x][y] = 1;
			}
		}
	}

	vector<vector<int>> answer;
	for (int i = 1; i <= n + 1; i++)
		for (int j = 1; j <= n + 1; j++) {
			if (row[i][j])
				answer.push_back({ i - 1, j - 1, 1 });
			if (col[i][j])
				answer.push_back({ i - 1, j - 1, 0 });
		}
	sort(answer.begin(), answer.end());
	return answer;
}

문제 :  카카오 2020 BLIND RECRUITMENT 가사 검색

트라이

 자료구조 트라이를 이용하면 문제에 접근하기는 쉬우나, 그냥 단순하게 트라이를 이용하면 시간초과 때문에 개고생하는 문제입니다. 개고생한 과정을 다뤄보겠습니다...

시도 1)

 그냥 트라이를 하나 선언하고 모든 words를 트라이에 insert 한 후 모든 queries를 트라이에서 find 하면서 가능한 모든 경우의 수를 카운트하며 탐색을 진행했다.

int find(const char* key) {
	int cnt = 0;
	if (*key == '\0' && finish == true)
		return 1;
	if (*key == '\0')
		return 0;

	if (*key == '?') {
		for (int i = 0; i < 26; i++)
			if (next[i] != NULL)
				cnt += next[i]->find(key + 1);
	}
	else {
		int curr = *key - 'a';
		if (next[curr] == NULL)
			return 0;
		cnt += next[curr]->find(key + 1);
	}
	return cnt;
}

  들어온 입력을 트라이에서 find 하면서 '?' 를 만나면 지금 노드에서 갈 수 있는 모든 경우를 카운트해줘야하므로 알파벳 소문자의 경우의 수 26가지를 다 탐색하며, 현재 노드에서 갈 수 있는 모든 노드로 다 이동하며 카운트를 해준다. 이러면, 시간 초과를 마주하게 된다. 단순하게 생각해보면 앞 쪽에 물음표들이 연달아 많이 나오는 경우는 처음부터 경우의 수가 굉장히 많아져서 시간 초과에 걸린다는 것을 알 수 있다. 예를 들어, "?????abc" 같은 경우를 find 하려면 최악의 경우 26^5을 다 타고 들어가게 된다.

시도 2)

트라이를 하나 더 선언했다. 그냥 트라이와 단어들을 reverse해서 저장하고 있는 트라이를 2개 이용해 queries 중에 앞이 '?' 이면 reverseTrie 에서 find를 하고, 아니라면 그냥 트라이에서 find를 진행했다.

 마찬가지로, 시간 초과를 마주하게 된다... "?????" 과 같이 모두 물음표인 경우 때문에 시간 초과에 걸린다는 것을 알 수 있었다. 

시도 3)

 길이가 i 인 단어들이 몇 개인지 애초에 미리 다 카운트해놓고, 시도2) 처럼 트라이 2개를 이용해서 문제를 해결하려했다. queries 중에 앞도 '?', 뒤도 '?' 라면 전체가 다 물음표인 경우이므로 그냥 길이가 같은 단어가 몇 개인지 return 해주고, 아니라면 트라이 2개를 이용해서 진행했다. 당연히 시간 초과에 봉착했다. 당연히, 앞 뒤가 모두 물음표는 아니지만 "a??????" 와 같이 한 글자만 문자가 나오고 뒤가 다 물음표가 나온다면 시도2)에서 개선된 점이 없다는 것을 알 수 있었다.

풀이 )

 결국 물음표를 만나면 탐색을 더 진행하는 것이 아니라 답을 바로 출력해줄 수 있어야된다는 것을 깨달았고, 같은 길이를 가진 words 들끼리 Trie를 선언해줬다. 그리고 trie 에 wordsCnt 라는 int형 변수를 추가해주고, insert 함수를 다음과 같이 수정했다.

	void insert(const char* key) {
		if (*key == '\0')
			finish = true;    //문자열이 끝나는 지점일 경우 표시
		else {
			int curr = *key - 'a';
			if (next[curr] == NULL)
				next[curr] = new Trie();    //탐색이 처음되는 지점일 경우 동적할당
			wordsCnt++;
			next[curr]->insert(key + 1);    //다음 문자 삽입
		}
	}

 즉, 현재 노드까지 겹치는 단어가 몇 개인지 insert 하면서 카운트를 진행했고, find 중 물음표를 만나면 바로 wordsCnt 값을 return 해주면서 끝내도록 개선했다.

#include<string>
#include<vector>
#include<cstring>
#include<algorithm>

using namespace std;

struct Trie {
	int wordsCnt;
	bool finish;    //끝나는 지점을 표시해줌
	Trie* next[26];    //26가지 알파벳에 대한 트라이
	Trie() {
		finish = false;
		wordsCnt = 0;
		memset(next, 0, sizeof(next));
	}
	~Trie() {
		for (int i = 0; i < 26; i++)
			if (next[i])
				delete next[i];
	}

	void insert(const char* key) {
		if (*key == '\0')
			finish = true;    //문자열이 끝나는 지점일 경우 표시
		else {
			int curr = *key - 'a';
			if (next[curr] == NULL)
				next[curr] = new Trie();    //탐색이 처음되는 지점일 경우 동적할당
			wordsCnt++;
			next[curr]->insert(key + 1);    //다음 문자 삽입
		}
	}

	int find(const char* key) {
		int cnt = 0;
		//cout << "현재 " << *key << "를 탐색중이고 " << wordsCnt << "는다음과같습니다.\n";
		if (*key == '\0' && finish == true)
			return 1;
		if (*key == '\0')
			return 0;

		if (*key == '?') {
			return wordsCnt;
		}
		else{
			int curr = *key - 'a';
			if (next[curr] == NULL)
				return 0;
			cnt += next[curr]->find(key + 1);
		}
		return cnt;
	}
};

vector<int> solution(vector<string> words, vector<string> queries) {
	Trie* trie[10001];
	Trie* reverseTrie[10001];
	for (int i = 1; i < 10001; i++){
		trie[i] = new Trie();
		reverseTrie[i] = new Trie();
	}

	for (int i = 0; i < words.size(); i++){
		trie[words[i].length()]->insert(words[i].c_str());
		reverse(words[i].begin(), words[i].end());
		reverseTrie[words[i].length()]->insert(words[i].c_str());
	}

	vector<int> answer;
	for (int i = 0; i < queries.size(); i++) {
		int ans;
        if(queries[i][0] == '?'){
			reverse(queries[i].begin(), queries[i].end());
			ans = reverseTrie[queries[i].length()]->find(queries[i].c_str());
		}
		else{
			ans = trie[queries[i].length()]->find(queries[i].c_str());
		}
		answer.push_back(ans);
	}
	return answer;
}

문제 : 2020 카카오 BLINE RECRUITMENT 자물쇠와 열쇠

구현

● 열쇠를 돌리고 옮겨가며 자물쇠와 맞는지 안맞는지 체크하면 된다.

● 열쇠는 기존의 상태, 90도 회전 상태, 180도 회전 상태, 270도 회전 상태 총 4가지 모양을 가질 수 있고, 기존의 상태부터 옮겨가며 현재 자물쇠와 맞는지 안맞는지 체크하고, 90도 회전한 후 다시 옮겨가며 현재 자물쇠와 맞는지 안맞는지 체크하고, 90도 더 회전한 후 다시 옮겨가며 체크하는 과정을 반복하면 된다.

● 열쇠를 회전하는 과정은 열쇠 배열을 그대로 복사한 후, 다음과 같은 식으로 회전해서 덮으면 된다.

for (int i = 0; i < N; i++)
	for (int j = 0; j < N; j++)
		key[i][j] = tempKey[N - 1 - j][i];

● 열쇠를 옮겨가며 자물쇠와 맞는지 안맞는지 체크하는 부분이 문제의 핵심인데, 열쇠랑 자물쇠가 한 칸이라도 겹치는 모든 (i , j) 에서 N x N 크기의 열쇠를 그리고 자물쇠와 겹치는 부분을 체크해주면 된다.

아래 그림과 같이 열쇠를 한 칸씩 이동해가며 모든 경우에 대해 자물쇠와 열쇠의 상태를 확인해주면 됩니다.

● 열쇠가 0인 부분은 자물쇠가 0이던 1이던 상관이 없고, 열쇠가 1일 때 자물쇠가 0이면 우리가 원하는 상황이고, 열쇠가 1일 때 자물쇠가 1이면  문제가 발생하므로 (열쇠, 자물쇠) 가 (1, 0) 이면 자물쇠의 상태를 1로 바꿔주고, (1, 1) 이면 자물쇠의 상태를 0으로 바꿔준다. 

#include <string>
#include <vector>

using namespace std;

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
	int rotation = 0, N = key.size(), M = lock.size();
	do {
		// check
		for (int i = -N + 1; i < M; i++) {
			for (int j = -N + 1; j < M; j++) {
				// (i , j) 에서 N x N key를 그린다고 생각.
				vector<vector<int>> tempLock(M);
				for (int k = 0; k < M; k++)
					for (int l = 0; l < M; l++)
						tempLock[k].push_back(lock[k][l]);

				for (int k = 0; k < N; k++) {
					for (int l = 0; l < N; l++) {
						if (0 <= (i + k) && (i + k) < M && 0 <= (j + l) && (j + l) < M) {
							if (tempLock[i + k][j + l] == 0 && key[k][l] == 1)
								tempLock[i + k][j + l] = 1;
							else if (tempLock[i + k][j + l] == 1 && key[k][l] == 1)
								tempLock[i + k][j + l] = 0;
						}
					}
				}
				// 제대로 만들어졌는지 체크하자.
				bool tempCheck = true;
				for (int k = 0; k < M; k++)
					for (int l = 0; l < M; l++)
						if (tempLock[k][l] == 0)
							tempCheck = false;
				if (tempCheck == true)
					return true;
			}
		}
		// 회전
		vector<vector<int>> tempKey(N);
		for (int i = 0; i < N; i++) 
			for (int j = 0; j < N; j++)
				tempKey[i].push_back(key[i][j]);
		for (int i = 0; i < N; i++) 
			for (int j = 0; j < N; j++) 
				key[i][j] = tempKey[N - 1 - j][i];

		rotation++;
	} while (rotation < 4);

	return false;
}

문제 : 2020 카카오 BLINE RECRUITMENT '괄호변환'

구현 문자열 스택

문제에서 정확하게 알고리즘을 명시해줘서 구현만 하면 되는 문제입니다.

1) 입력으로 들어온 문자열이 빈 문자열인지 아닌지 체크, 빈 문자열이라면 빈 문자열을 return 해줍니다.

2) 입력으로 들어온 문자열을 순회하며, '(' 와 ')' 의 개수를 count하고 빈 문자열 u에 concat을 해줍니다. 이때, '(' 와 ')' 의 개수가 같아지면 u가 균형잡힌 괄호 문자열이므로 break 해주고, 나머지 부분은 v 에 concat을 해줍니다.

3) u가 올바른 괄호 문자열인지 자료구조 stack 을 이용해 check합니다.

 3-1) u가 올바른 괄호 문자열이라면 u + solution(v) 를 return 해주면 됩니다.

 3-2) u가 올바른 괄호 문자열이 아니라면, '(' + solution(v) + ')' 와 u의 첫 번째와 마지막 문자를 제거한 나머지 부분들 뒤집어서 return 해주면 됩니다.

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

string solution(string p) {
	string answer = "";
	string u = "", v = "";

	if (p == "")
		return answer;
	
	// u 랑 v로 나눔.
	int cnt1 = 0, cnt2 = 0;
	for (int i = 0; i < p.length(); i++) {
		if (p[i] == '(')
			cnt1++;
		else
			cnt2++;

		u += p[i];
		if (cnt1 != 0 && cnt1 == cnt2)
			break;
	}

	for (int i = u.length(); i < p.length(); i++)
		v += p[i];
	
	// u 가 올바른 괄호 문자열인지 체크하자.
	bool check = false;
	stack<char> s;
	for (int i = 0; i < u.length(); i++) {
		if (u[i] == '(')
			s.push(u[i]);
		else {
			if (s.empty()) {
				check = true;
				break;
			}
			s.pop();
		}
	}
	if (!s.empty())
		check = true;
	if (!check) { // u가 올바른 괄호 문자열
		answer = answer + u + solution(v);
	}
	else {
		string temp = "";
		for (int i = 1; i < u.length() - 1; i++)
			if (u[i] == '(')
				temp += ')';
			else
				temp += '(';
		answer = answer + '(' + solution(v) + ')' + temp;
	}
	return answer;
}