자물쇠와 열쇠
실제로 시험을 봤었는데 , 그때 어려워 보여서 안풀고 넘어갔다.
문제의 목적은 키가 락에 들어 맞는지 확인하는 것이다.
방법은 키를 회전, 이동시켜서 확인하면 된다. 문제에 주어짐.....
근데 문제는 회전 구현이 어려워 보인다.
회전을 어떻게 하지??-> 음 row, col의 위치를 교환하면 되는거 같다!!... -> 근데 이건 0,0이 왼쪽 위로 기준이 고정됬을때다.
그러면 회전하고 이동시킨다 치고...?이동도 어떻게 해야되지?? -> 이동 시키려면 키를 없애면 안되고 범위를 정해서 이동시켜야 한다.?무슨 말이지 ㅋㅋ -> root_r ,root_c , 배열 크기인 n을 사용해서 전체 배열을 이동시키기 보다 세 변수의 변경을 이동으로 처리하자.
홈에 맞는지 확인은 어떻게 하지?? -> 왼쪽 위 끝을 키(root_r,root_c)와 락(0,0)을 일치시키고, 모든 키에서 1인곳이 락에서 0이고 락에서 0인곳이 키에서 1이여야 한다. 이 두가지 사실이 모두 참이여야 한다.
자 이제 회전만 시키면 된다...... -> r,c 사이의 규칙이 있는거 같다. ->행은 열로 바뀌고, 열도 행으로 바뀐다. -> 근데 nxn 에서 (r,c)이면 (n-c,n-r)로 변경된다.
자 이제 회전 ,이동을 이용해 완전 탐색을 해보자. 90도 회전 ->전체 확인 ->90도 회전->전체 확인->90도 회전->전체 확인. 이렇게 하면 되지 않나?
음 실패 했다. 이유는 잘 모르겠다. 디버깅도 너무 어렵고........ 틀린 이유에 대한 추측은 90도 회전 -> root : -20 ~20으로 바꾸면서 하고 다시 90도 회전할때 원본으로 시작해야 되는데 root가 바뀐걸로 하니까 회전이 초기 키의 전체에 대해서 안되고 이동된 키의 일부만 회전되는거 같다.
틀린 코드.
#include <string>
#include <vector>
#include<iostream>
using namespace std;
int root_r = 40, root_c=40;
int arr[100][100] = { 0 };
int brr[100][100] = { 0 };
int n;
void rotate90() {
//회전
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
brr[n - j][n - i] = arr[i][j];
}
}
//다시 arr에 넣어.
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
arr[i][j] = brr[i][j];
}
}
}
bool check(vector<vector<int>>lock) {
//compare lock and arr
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
//key는 잇고 락은 막혀있는 경우.
//cout << i + root_r << " " << j + root_c<<"\n";
if (arr[i + root_r][j + root_c] == 1 && lock[i][j] == 1) {
//cout << i + root_r << " " << j + root_c << "\n";
return false;
}
else if (lock[i][j] == 0 && arr[i + root_r][j + root_c] == 0) {
//cout << i + root_r << " " << j + root_c << "\n";
return false;
}
}
}
return true;
}
bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
bool answer = true;
n = key.size();
for (int i = 0; i < 3; i++) {
for (int v = 0; v < n; v++)
{
for (int j = 0; j < n; j++)
{
arr[root_r + v][root_c + v] = key[v][j];
}
}
rotate90();
int nr, nc;
nr = root_r;
nc = root_c;
for (int j = -20; j <= 20; j++) {
for (int k = -20; k <= 20; k++) {
root_r = nr + j;
root_c = nc + k;
if (check(lock)) {
answer = true;
break;
}
else {
answer = false;
}
}
}
root_r = nr;
root_c = nc;
}
return answer;
}
다시 시도해 본다.
음 근데 틀렸다. 회전이 잘 안됬었다. rotate90을 수정했다.
#include <string>
#include <vector>
#include<iostream>
using namespace std;
int root_r = 40, root_c = 40;
int arr[100][100] = { 0 };
int brr[100][100] = { 0 };
int n;
void rotate90() {
//회전
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
brr[j][n -1 - i] = arr[i+root_r][j+root_c];
}
}
//다시 arr에 넣어.
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
arr[i+root_r][j+root_c] = brr[i][j];
}
}
}
void printarr() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << arr[root_r+ i][root_c + j] << " ";
}
cout << "\n";
}
cout << "\n";
}
bool check(vector<vector<int>>lock) {
int sum = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (lock[i][j] == 1) {
sum += 1;
}
}
}
if (sum == n * n) {
return true;
}
//compare lock and arr
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
//key는 잇고 락은 막혀있는 경우.
//cout << i + root_r << " " << j + root_c<<"\n";
if (arr[i + root_r][j + root_c] == 1 && lock[i][j] == 1) {
//cout << i + root_r << " " << j + root_c << "\n";
return false;
}
else if (lock[i][j] == 0 && arr[i + root_r][j + root_c] == 0) {
//cout << i + root_r << " " << j + root_c << "\n";
return false;
}
}
}
return true;
}
bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
bool answer = true;
n = key.size();
for (int i = 0; i < 4; i++) {
for (int v = 0; v < n; v++)
{
for (int j = 0; j < n; j++)
{
arr[root_r + v][root_c + j] = key[v][j];
}
}
//printarr();
for (int k = 0; k < i; k++) {
rotate90();
}
//printarr();
int nr, nc;
nr = root_r;
nc = root_c;
for (int j = -20; j <= 20; j++) {
for (int k = -20; k <= 20; k++) {
root_r = nr + j;
root_c = nc + k;
if (check(lock)) {
answer = true;
return answer;
}
else {
answer = false;
}
}
}
root_r = nr;
root_c = nc;
}
return answer;
}
그런데 94점 ,3개 틀렸다. 뭐가 틀린지 모르겠다...... -> 일단 한개 찾았다. 이중 반복문에서 키를 꼭 상하좌우 20씩 움직이면 안되고 n개씩 움직여야 한다.... -> 시간 단축에 의미 , 틀렸다 ㅋㅋ.
| 테스트 25 〉 | 실패 (0.03ms, 3.83MB) |
| 테스트 29 〉 | 실패 (0.10ms, 3.82MB) |
| 테스트 31 〉 | 실패 (0.03ms, 3.79MB) |
틀린거 같은 이유를 하나 더 찾았다.
- key는 M x M(3 ≤ M ≤ 20, M은 자연수)크기 2차원 배열입니다.
- lock은 N x N(3 ≤ N ≤ 20, N은 자연수)크기 2차원 배열입니다.
- M은 항상 N 이하입니다
key랑 lock의 크기가 같다고 간주 했다. 그리고 정사각행렬이라는 것도 어떻게 보면 당연한건 아니다.
이 부분 때문에 음 같은지 root를 바꾸며 (즉 키를 이동시키며 비교하는 부분은 동일할 거 같다.) 하지만 회전할때는 키 행렬의 크기를 알아야 한다. -> 이래도 틀렸다. 음....
틀린 코드...
#include <string>
#include <vector>
#include<iostream>
using namespace std;
int root_r = 40, root_c = 40;
int arr[100][100] = { 0 };
int brr[100][100] = { 0 };
int m,n;
void rotate90() {
//회전
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
brr[j][n - 1 - i] = arr[i + root_r][j + root_c];
}
}
//다시 arr에 넣어.
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
arr[i + root_r][j + root_c] = brr[i][j];
}
}
}
void printarr() {
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
cout << arr[root_r + i][root_c + j] << " ";
}
cout << "\n";
}
cout << "\n";
}
bool check(vector<vector<int>>lock) {
int sum = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (lock[i][j] == 1) {
sum += 1;
}
}
}
if (sum == n * n) {
return true;
}
//compare lock and arr
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
//key는 잇고 락은 막혀있는 경우.
//cout << i + root_r << " " << j + root_c<<"\n";
if (arr[i + root_r][j + root_c] == 1 && lock[i][j] == 1) {
//cout << i + root_r << " " << j + root_c << "\n";
return false;
}
else if (lock[i][j] == 0 && arr[i + root_r][j + root_c] == 0) {
//cout << i + root_r << " " << j + root_c << "\n";
return false;
}
}
}
return true;
}
bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
bool answer = true;
m = key.size();
n = lock.size();
for (int i = 0; i < 4; i++) {
for (int v = 0; v < m; v++)
{
for (int j = 0; j < m; j++)
{
arr[root_r + v][root_c + j] = key[v][j];
}
}
//printarr();
for (int k = 0; k < i; k++) {
rotate90();
}
//printarr();
int nr, nc;
nr = root_r;
nc = root_c;
for (int j = -n; j <= n; j++) {
for (int k = -n; k <= n; k++) {
root_r = nr + j;
root_c = nc + k;
if (check(lock)) {
answer = true;
return answer;
}
else {
answer = false;
}
}
}
root_r = nr;
root_c = nc;
}
return answer;
}
틀린 부분을 발견했다. 내가 이전에 키 행렬 크기랑 락 행렬 크기가 다른걸 수정하면서
brr[j][n-1-i] 이 부분을 안 고쳤었다.... 문제 해결을 구상할때 사용하는 변수들을 더 정확하게 명시하는 편이 좋겠다.
void rotate90() {
//회전
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
brr[j][m - 1 - i] = arr[i + root_r][j + root_c];
}
}
//다시 arr에 넣어.
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
arr[i + root_r][j + root_c] = brr[i][j];
}
}
}
이제 다른 사람 코드를 보고 있다. 다른 분은 회전의 결과인 rotate를 rotate[4][m][m] 처럼 4가지 경우를 배열에 저장함으로서 반복문에서 사용 가능하게 구현했다. 나는 매 순간 마다 구해야 되서 코드 구현상 반복문 사용이 좀 어렵다.
그리고 다른 사람들은 6중 반복문으로 구현한게 대부분인데 잘 이해가 안된다 내가 자주 하던 방식이 아니라서, 하지만 완전 탐색에서 반복문으로 푸는게 시간상 더 좋다는 의견이 있으니까 받아들이도록 노력해 보겠다.....
그리고 이런식으로 구현하면 나처럼 root를 사용하는 방식이 아니여도 홈에 맞는지 비교할 수 있다.
for (int r = 0; r < 4; ++r) {
for (int ii = 0; ii < m; ++ii) {
if (i + ii < 0 || i + ii >= n) continue;
for (int jj = 0; jj < m; ++jj) {
if (j + jj < 0 || j + jj >= n) continue;
if (keyr[r][ii][jj] + lock[i + ii][j + jj] != 1) {
goto next;
}
}
}
}
내 생각에 문제 잘 풀려면 문제를 분석하고 거기서 해결의 길을 찾는 과정을 연습해야 하는거 같다. 위처럼 구현한 분들은 락과 키가 매치가 되는지 고민하는 과정에서 키를 mxm으로 고정했을때 어떻게 해야 락의 홈에 끼워지는지 방법을 고민해서 위처럼 해결한거 같다. 난 반대로 키를 크게 잡고 락에 끼우는 방법을 생각했는데 어떻게 이 둘이 자유 자재로 고민될까 난 왜 이것만 떠올랐지.... 사실 대칭적으로 생각하면 매우 단순한 문제다...
가사 검색
자신이 좋아하는 노래가사에 사용된 단어들 중에 특정 키워드가 몇개 포함되어 있는지 알아내는 프로그램을 개발해 달라합니다. 이때 키워드의 와일드카드 문자중 하나인 ?가 포함된 패턴 형태의 문자열을 뜻합니다.
가사에 사용된 모든 단어들이 담긴 배열 words와 찾고자 하는 키워드가 담긴 배열 queries가 주어질 때, 각 키워드 별로 매치된 단어가 몇 개인지 순서대로 배열에 담아 반환해 보자.
이때 words의 길이는 2이상 십만 이하입니다. 각 가사 단어의 길이는 1이상 10,000 이하로 빈 문자열인 경우는 없다.
전체 가사 단어 길이의 합은 2이상 백만 이하입니다. 가사에 동일 단어가 여러번 나올 경우 중복을 제거하고 words에는 하나로만 제공된다.
쿼리 제한 사항 2이상 십만 이하입니다. 각 검색 키워드의 길이는 1이상 만 이하로 빈 문자열인 경우는 없다.
전체 검색 키워드 길이의 합은 2이상 백만 이하입니다. 검색 키워드는 중복될 수도 있습니다. ??는 접두사나 접미사 둘중 하나로만 올 수 있습니다.
갯수가 words 10만개 , queries 10만 개여서 음 n^2 방식은 절대 안되고 , nlogn까지만 될거 같다.
음 일단 문자열이 일치하는지 확인해야 한다. 그래서 생각난 알고리즘이 두개가 있는데 kmp랑 trie 자료구조이다.
근데 kmp는 찾아보니 한 문장에서 해당 문자열이 있는지 찾는데 이용된다. 그리고 그 시간이 O(N+M)으로 매우 짧다.
그렇다면 트라이일 가능성이 높은듯 .
트라이는 문자열에서 검색 시간이 문자열의 길이인 M , O(M)이라 한다.
내 생각에는 워드에서 가장 긴 문자의 길이가 10의 4승 , 그리고 쿼리에서의 단어의 갯수는 10의 5승이므로 둘이 곱하면 10의 9승이니까 시간은 1초안에 들어올거 같다.
그리고 구현은 find에서 key+1이 ?이면 그만 찾고 아래에 존재하는 종료 노드의 갯수를 세주면 된다. 그런데 음 종료 노드 갯수를 노드의 분할 지점마다 저장해야 될거 같은데 그건 어려워 보이네? -> 이건 인저트 할때 각 노드에 cnt를 1씩 추가해 주면 된다. cnt는 이 노드에 붙은 단어의 갯수이다.
-> 이 부분이 문제다. cnt는 뒤에 남은 글자수에 상관 없이 앞에만 맞으면 맞도록 해버렸다.....
-> 그러지 말고 그냥 끝까지 확인하도록 해야 될거 같다 -> 이러면 경우가 너무 많아진다. -> 트라이를 문자열 길이마다 각각 저장하는건 어떨까. -> 예제만 맞고 세그멘테이션 폴트가 떳다ㅋㅋ .... ->이건 결국 그냥 내가 코드 잘못짠걸로....
그리고 문제가 matul이 워드고 쿼리가 ???ul 이면 내생각에는 뒤로 검색해야 될거 같다. 즉 l -> u -> m ->a ->t, 트라이를 문자열을 거꾸로 넣은거에서 ??가 접두사에 오는 것은 거꾸로 검색해서 , 반대로 ???가 접미사에 오는 놈들은 그냥 앞에서 구하면 될거 같다. 그럼 ????? 처럼 전부 ?인 놈은 일일이 찾은 단어를 절반으로 만들자.
이제 구현중이다. 문제는 워드는 스트링으로 들어와 있는데 내가 본 코드의 트라이는 char*형을 사용했다. string을 char*로 바꿀지 트라이를 변경할지 고민중이다.
#include <string>
#include <vector>
#include<stdlib.h>
#include<string.h>
#include<iostream>
using namespace std;
struct Trie {
bool finish;
int cnt=1;
Trie * next[26];
Trie() : finish(false) {
memset(next, 0, sizeof(next));
}
~Trie() {
for (int i = 0; i < 26; i++) {
if (next[i])
delete next[i];
}
}
void insert(char* key) {
if (*key == '\0') {
finish = true;
}
else {
int curr = *key - 'a';
if (next[curr] == NULL)
next[curr] = new Trie();
else {
next[curr]->cnt += 1;
}
next[curr]->insert(key + 1);
}
}
Trie * find(char * key) {
if (*key == '\0' || *key == '?') return this;
int curr = *key - 'a';
if (next[curr] == NULL) return NULL;
return next[curr]->find(key + 1);
}
};
struct Trie tri_post[100001];
struct Trie tri_pre[100001];
char aWord[10001];
int anss[100001] = { 0 };
vector<int> solution(vector<string> words, vector<string> queries) {
vector<int> answer;
//post : ada??
for (int i = 0; i < words.size(); i++) {
for (int j = 0; j < words[i].size(); j++) {
aWord[j] = words[i][j];
aWord[j + 1] = '\0';
}
tri_post[words[i].size()].insert(aWord);
}
for (int i = 0; i < queries.size(); i++) {
if (queries[i][queries.size() - 1] == '?') {
for (int j = 0; j < queries[i].size(); j++) {
aWord[j] = queries[i][j];
aWord[j + 1] = '\0';
}
int ans = tri_post[queries[i].size()].find(aWord)->cnt;
anss[i] = ans;
}
}
//pre : ??ads
for (int i = 0; i < words.size(); i++) {
for (int j = 0; j <words[i].size(); j++) {
aWord[words[i].size()- 1 -j] = words[i][j];
}
aWord[words[i].size()] = '\0';
tri_pre[words[i].size()].insert(aWord);
}
for (int i = 0; i < queries.size(); i++) {
if (queries[i][0] == '?' && queries[i][queries.size()-1] != '?') {
for (int j = 0; j < words[i].size(); j++) {
aWord[queries[i].size() - 1 - j] = queries[i][j];
}
aWord[words[i].size() ] = '\0';
int ans = tri_pre[queries[i].size()].find(aWord)->cnt;
anss[i] = ans;
}
}
for (int i = 0; i < queries.size(); i++) {
answer.push_back(anss[i]);
}
return answer;
}
void main() {
vector<string> words;
vector<string> queries;
words.push_back("frodo");
words.push_back("front");
words.push_back("frost");
words.push_back("frozen");
words.push_back("frame");
words.push_back("kakao");
queries.push_back("fro??");
queries.push_back("????o");
queries.push_back("fr???");
queries.push_back("fro???");
queries.push_back("pro?");
vector<int> ans_main;
ans_main = solution(words, queries);
for (int i = 0; i < ans_main.size(); i++) {
cout << ans_main[i] << "\n";
}
}아 내가 자주 하는 실수인데 복붙해서 코드를 작성하다가 post, pre tri 바꿔 쓰고, quries[i].size() 대신에 quries.size()로 바꿨고 ㄷㄷ...... 아 코드도 잘짜야되는데
근데 어쨌든 다시짠거는 효율성 한개 틀림... 아 왜틀렸지....
#include <string>
#include <vector>
#include<stdlib.h>
#include<string.h>
#include<iostream>
using namespace std;
struct Trie {
bool finish;
int cnt = 1;
Trie * next[26];
Trie() : finish(false) {
memset(next, 0, sizeof(next));
}
~Trie() {
for (int i = 0; i < 26; i++) {
if (next[i])
delete next[i];
}
}
void insert(char* key) {
if (*key == '\0') {
finish = true;
}
else {
int curr = *key - 'a';
if (next[curr] == NULL)
next[curr] = new Trie();
else {
next[curr]->cnt += 1;
}
next[curr]->insert(key + 1);
}
}
Trie * find(char * key) {
if (*key == '\0' || *key == '?') return this;
int curr = *key - 'a';
if (next[curr] == NULL) return NULL;
return next[curr]->find(key + 1);
}
};
struct Trie tri_post[100001];
struct Trie tri_pre[100001];
char aWord[10001];
int anss[100001] = { 0 };
struct Trie *tmp;
vector<int> solution(vector<string> words, vector<string> queries) {
vector<int> answer;
int ans;
//post : ada??
for (int i = 0; i < words.size(); i++) {
for (int j = 0; j < words[i].size(); j++) {
aWord[j] = words[i][j];
}
aWord[words[i].size()] = '\0';
tri_post[words[i].size()].insert(aWord);
}
for (int i = 0; i < queries.size(); i++) {
if (queries[i][queries[i].size() - 1] == '?') {
for (int j = 0; j < queries[i].size(); j++) {
aWord[j] = queries[i][j];
}
aWord[queries[i].size()] = '\0';
if ((tmp = tri_post[queries[i].size()].find(aWord)) != NULL) {
ans = tmp->cnt;
}
else {
ans = 0;
}
anss[i] = ans;
}
}
//pre : ??ads
for (int i = 0; i < words.size(); i++) {
for (int j = 0; j <words[i].size(); j++) {
aWord[words[i].size() - 1 - j] = words[i][j];
}
aWord[words[i].size()] = '\0';
tri_pre[words[i].size()].insert(aWord);
}
for (int i = 0; i < queries.size(); i++) {
if (queries[i][0] == '?' && queries[i][queries[i].size() - 1] != '?') {
for (int j = 0; j < queries[i].size(); j++) {
aWord[queries[i].size() - 1 - j] = queries[i][j];
}
aWord[queries[i].size()] = '\0';
if ((tmp = tri_pre[queries[i].size()].find(aWord)) != NULL) {
ans = tmp->cnt;
}
else {
ans = 0;
}
anss[i] = ans;
}
}
for (int i = 0; i < queries.size(); i++) {
answer.push_back(anss[i]);
}
return answer;
}
void main() {
vector<string> words;
vector<string> queries;
words.push_back("frodo");
words.push_back("front");
words.push_back("frost");
words.push_back("frozen");
words.push_back("frame");
words.push_back("kakao");
queries.push_back("fro??");
queries.push_back("????o");
queries.push_back("fr???");
queries.push_back("fro???");
queries.push_back("pro?");
vector<int> ans_main;
ans_main = solution(words, queries);
for (int i = 0; i < ans_main.size(); i++) {
cout << ans_main[i] << "\n";
}
}예외를 찾았다. 왠지 이 부분 제대로 생각 안하고 구현한거 같아서 빈틈이 있을거 같긴했다......쉬운게 없넹....
words.push_back("frodo");
words.push_back("front");
words.push_back("frost");
words.push_back("frozen");
words.push_back("frame");
words.push_back("kakao");
queries.push_back("?????");
queries.push_back("??????");
cnt 부분을 제대로 수정해 주었다.
#include <string>
#include <vector>
#include<stdlib.h>
#include<string.h>
using namespace std;
struct Trie {
bool finish;
int cnt=0;
Trie * next[26];
Trie() : finish(false) {
memset(next, 0, sizeof(next));
}
~Trie() {
for (int i = 0; i < 26; i++) {
if (next[i])
delete next[i];
}
}
void insert(char* key) {
if (*key == '\0') {
finish = true;
}
else {
int curr = *key - 'A';
if (next[curr] == NULL)
next[curr] = new Trie();
else {
next[curr]->cnt += 1;
}
next[curr]->insert(key + 1);
}
}
Trie * find(char * key) {
if (*key == '\0' || *key == '?') return this;
int curr = *key - 'A';
if (next[curr] == NULL) return NULL;
return next[curr]->find(key + 1);
}
};
struct Trie tri_post;
struct Trie tri_pre;
char aWord[10001];
int anss[100001] = { 0 };
vector<int> solution(vector<string> words, vector<string> queries) {
vector<int> answer;
//post : ada??
for (int i = 0; i < words.size(); i++) {
for (int j = 0; j < words[i].size(); j++) {
aWord[j] = words[i][j];
}
tri_post.insert(aWord);
}
for (int i = 0; i < queries.size(); i++) {
if (queries[i][queries.size() - 1] == '?') {
for (int j = 0; j < queries[i].size(); j++) {
aWord[j] = queries[i][j];
}
int ans = tri_post.find(aWord)->cnt;
anss[i] = ans;
}
}
//pre : ??ads
for (int i = 0; i < words.size(); i++) {
for (int j = words[i].size()-1; j >=0; j++) {
aWord[words.size()- 1 -j] = words[i][j];
}
tri_pre.insert(aWord);
}
for (int i = 0; i < queries.size(); i++) {
if (queries[i][0] == '?' && queries[i][queries.size()-1] != '?') {
for (int j = queries[i].size() - 1; j >= 0; j++) {
aWord[queries.size() - 1 - j] = queries[i][j];
}
int ans = tri_pre.find(aWord)->cnt;
anss[i] = ans;
}
}
return answer;
}
다른 사람의 코드를 분석해 보았다.
일단 트라이 구조에서 다른 점은 '?'가 노드로 들어올 수 있도록 하였다.
find에서 '?'노드가 null이 아니면 '?'노드를 통해서도 다음 키 값 즉 key+1도 찾도록 했다. 즉 이 부분은 ?여도 그냥 찾은셈치고 계속 찾으라는거. 그리고 마지막 노드에서만 cnt++를 수행한다.
그리고 추가로 getCnt 메소드가 있다. 쿼리를 입력해서 트라이에서 마지막 노드를 찾고 그 마지막 노드의 cnt를 리턴한다.
메인에서는 trie를 한개만 선언했고, queries를 먼저 인저트 하고 words를 find를 통해서 매치되는 노드의 마지막 cnt에 1씩 더해주었다. 그리고 getCnt로 트라이에서 쿼리와 맞는 단어의 갯수를 찾았다.
이 분은 효율성 시간이.
| 테스트 1 〉 | 통과 (11.91ms, 11.5MB) |
| 테스트 2 〉 | 통과 (166.17ms, 52.3MB) |
| 테스트 3 〉 | 통과 (8.83ms, 13.7MB) |
| 테스트 4 〉 | 통과 (292.56ms, 57.1MB) |
| 테스트 5 〉 | 통과 (260.28ms, 182MB) |
내것은
| 테스트 1 〉 | 통과 (70.71ms, 152MB) |
| 테스트 2 〉 | 통과 (159.84ms, 255MB) |
| 테스트 3 〉 | 통과 (124.08ms, 238MB) |
| 테스트 4 〉 | 통과 (167.86ms, 274MB) |
| 테스트 5 〉 | 통과 (287.00ms, 478MB) |
내것이 좀 더 빠르지 않을까 했는데 아니였다. 용량만 많이씀....
해쉬로 풀은 사람도 있다. 음 frodo면 키로 frod? , fro?? ,fr???, f????, ????? 맵에 모두 넣고(????o, ???do 이런식으로도 넣는다.) 쿼리를 키로 해서 매치되는 것을 맵에서 찾는다.
해쉬로 푼거 시간 (문자열 길이에 따라 그냥 막 일일이 비교한 것도 있어서 약간 느린것도 있는거 같은데 해쉬가 훨씬 효율이 좋아 보인다. 넣는데는 문자열 길이 * 문자 갯수지만 검색 시간이 O(1)이라 시간이 단축되는듯?)
| 테스트 1 〉 | 통과 (260.75ms, 40.9MB) |
| 테스트 2 〉 | 통과 (989.26ms, 113MB) |
| 테스트 3 〉 | 통과 (567.76ms, 69.7MB) |
| 테스트 4 〉 | 통과 (10.19ms, 7.95MB) |
| 테스트 5 〉 | 통과 (13.37ms, 8.83MB) |
내가 문제 풀던 중 워드랑 쿼리를 비교하려 했던 부분에서 다르게 해결한것 같다.... 나는 쿼리 한개에서 워드들에서 매치되는게 몇개인지 세어볼려했는데, 이 부분에서 쿼리에 매치되는 워드를 맵에 저장할 생각을 하다니.....으
내가 할일.
트라이 자료구조 구현할 수 있기, 어느정도 암기가 필요할듯.
'알고리즘 문제 풀기' 카테고리의 다른 글
| 백준 - 1725번 히스토그램,6549 히스토그램에서 가장 큰 직사각형 (0) | 2020.01.03 |
|---|---|
| 프로그래머스 - 카카오 2020 블라인드 테스트 (블록 이동하기, 문자열 압축) (0) | 2020.01.02 |
| 프로그래머스 - 스택/큐 : 프린터, 쇠막대기, 주식 가격 (0) | 2019.12.30 |
| 프로그래머스 - 스택 : 탑, 다리를 지나는 트럭, 기능개발 (0) | 2019.12.27 |
| 프로그래머스 - 해쉬 (0) | 2019.12.26 |