https://programmers.co.kr/learn/courses/30/lessons/60060

 

코딩테스트 연습 - 가사 검색 | 프로그래머스

 

programmers.co.kr

 

트라이로 푼 문제

 

find를 비재귀로 했다가 효율성 3번만 계속 틀렸다

 

진짜 미쳐버리는줄 알았다 시간도 더빠르고 메모리도 동일한데 뭐가 문제란 말인지

 

정확성 테스트에서 예외 확인하고 효율성에서 시간 확인하는게 아닌건가??

 

맞왜틀

 

진자로 너무 화가낫다..

 

발상 자체는 금방 했는데 저 3번때문에 며칠을 꼬라박았다

 

답은 재귀였다.

 

아나

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
struct Trie
{
    Trie()
    {
        memset(next, 0, sizeof(next));
        /*for (int i = 0; i < 26; ++i)
        {
            next[i] = nullptr;
        }*/
    }
    ~Trie()
    {
        for (int i = 0; i < 26; ++i)
        {
            if (next[i])
            {
                //std::cout << (char)('a' + i);
                delete next[i];
                //std::cout << '\n';
            }
        }
    }
 
    void insert(const char* word)
    {
        if (*word == '\0')
        {
            return;
        }
        ++size;
 
        int idx = *word - 'a';
        if (next[idx] == nullptr)
        {
            next[idx] = new Trie;
        }
        next[idx]->insert(word + 1);
    }
 
    unsigned int find_how_many(const char* word)
    {
        //엉뚱한 글자가 나오면 0을 리턴합니다
        if (next[word[0] - 'a'] == nullptr)
        {
            return 0;
        }
        // "?????"같은 상황을 대비해 첫글자가 '\0'이라면 해당 글자수의 모든 사이즈를 리턴합니다
        //if (*word == '\0')
        if (*word == '?')
        {
            return size;
        }
        
        //word를 따라가기 위한 idx 변수를 만듭니다.
        unsigned int idx = 0;
        //트라이의 링크를 따라가기 위한 tour변수를 만들었습니다.
        Trie* tour = next[word[idx++] - 'a'];
        //'f????'같은 상황을 대비해 idx를 올리고 검사합니다.
        //if (word[idx] == '\0')
        if (word[idx] == '?')
        {
            return tour->size;
        }
 
        //word와 트라이 링크를 같이 따라갑니다
        while (tour->next[word[idx] - 'a'] != nullptr)
        {
            tour = tour->next[word[idx++] - 'a'];
 
            //if (word[idx] == '\0')
            if (word[idx] == '?')
            {
                //word의 끝이 나오면 사이즈를 리턴합니다
                return tour->size;
            }
        } 
        return 0;
    }
 
    //unsigned int find_how_many(const char* word)
    //{
    //    if (*word == '?')
    //    {
    //        return size;
    //    }
    //    if (next[word[0] - 'a'] == nullptr)
    //    {
    //        return 0;
    //    }
 
    //    return next[word[0] - 'a']->find_how_many(word + 1);
    //}
 
public:
    Trie* next[26];
    unsigned int size = 0;
};
 
Trie trieArr[10001];
Trie rtrieArr[10001];
 
vector<int> solution(vector<string> words, vector<string> queries) {
    vector<int> answer(queries.size());
    //std::unordered_map<int, Trie> trieArr;
    //std::unordered_map<int, Trie> rtrieArr;
    //trieArr.reserve(10010);
    //rtrieArr.reserve(10010);
 
    std::string token;
    for (auto& it : words)
    {
        //입력받은 단어를 정방향으로 한번, 역방향으로 한번 넣었습니다.
        token.clear();
        token = it;
        std::reverse(token.begin(), token.end());
        rtrieArr[it.size()].insert(token.c_str());
        trieArr[it.size()].insert(it.c_str());
    }
 
    int idx = 0;
    for (auto& it : queries)
    {
        //첫글자가 ?이 아니면 정방향, ?이 나올때까지 쿼리의 단어를 token에 넣고 find를 돌렸습니다
        token.clear();
        if (it.front() != '?')
        {
 
            //int i = 0;
            //while (it[i] != '?')
            //{
            //    token += it[i++];
            //}
            //token += '\0';
            
            //answer[idx++] = trieArr[it.size()].find_how_many(token.c_str());
            
            answer[idx++] = trieArr[it.size()].find_how_many(it.c_str());
        }
        else
        {
            //첫글자가 ?이면 역방향, 위와 마찬가지로 ?가 나올때까지 역방향으로 token에 넣고 find 함수에 넣었습니다
            
            std::reverse(it.begin(), it.end());
            //int i = it.size() - 1;
            //while (it[i] != '?')
            //{
            //    token += it[i--];
            //}
            //token += '\0';
 
            //answer[idx++] = rtrieArr[it.size()].find_how_many(token.c_str());
            
            answer[idx++] = rtrieArr[it.size()].find_how_many(it.c_str());
        }
    }
    return answer;
}
 
int main()
{
    std::vector<std::string> words = { "frodo", "front", "frost", "frozen", "frame", "kakao" };
    std::vector<std::string> queries = { "fro??", "????t", "fr???", "fro???", "pro?" };
    for (auto it : solution(words, queries))
    {
        std::cout << it << ' ';
    }
    return 0;
}
 cs

문제의 틀린 답. 주석처리 된 find_how_many 재귀함수를 사용하면 정답이다.

저작자표시

'알고리즘' 카테고리의 다른 글

이분탐색  (0) 2020.03.05
카카오 2020 5번 - 기둥과 보(구현)  (0) 2020.02.16
백준 2658: 직각이등변삼각형찾기(구현)  (0) 2020.02.01
카카오 2020 3번 - 자물쇠와 열쇠(주석미완)  (0) 2020.02.01
백준 2667: 단지번호붙이기 (플러드필, dfs)  (0) 2019.12.15

https://www.acmicpc.net/problem/2658

 

2658번: 직각이등변삼각형찾기

입력된 모양이 직각이등변 삼각형을 이루는 경우에는 세 꼭짓점의 위치를 출력하고, 그렇지 않은 경우에는 0을 출력한다. 각 꼭짓점의 위치를 한 줄에 두 개의 수로 출력한다. 두 수는 하나의 빈 공백을 두고 출력한다. 첫째 수는 그 꼭짓점이 위에서부터 몇 번째 줄에 있는가 나타내며, 두 번째 수는 왼쪽부터 몇 번째 칸에 있는가를 나타내야 한다. 꼭짓점을 출력할때는 첫째 수가 작은 것부터, 첫째 수가 같을 경우 두 번째 수가 작은 것부터 출력한다.

www.acmicpc.net

 

진짜 머리 쥐어뜯으면서 구현함. 카카오 2020 3번보다 어려웠음..

 

알고리즘 오픈챗에서 누군가가 자기는 위치, 크기, 각도별로 모든 삼각형을 다 만들어서 하나씩 비교했을것같다고 말했는데

 

나는 어케 만들어야할지 감도 안오고 해서 일단 하던대로 진행함

 

그리고 성공하자마자 제출하고 추후에 코드정리는 따로 안해서 성공 당시 그대로의 코드임, 굉장히 난잡하고 더러움

 

그래도 해내서 행복함

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
 
struct pos
{
    int x;
    int y;
};
 
char arr[11][11];
char visit[11][11];
int dy[8] = { -1, -1, 0, 1, 1,  1,  0, -1 };
int dx[8] = {  0,  1, 1, 1, 0, -1, -1, -1 };
bool isFilled = true;
std::vector<pos> tri;
 
bool cmp(const pos& first, const pos& second)
{
    if (first.y < second.y)
        return true;
    else if (first.y == second.y)
        return first.x < second.x;
    else
        return false;
}
 
void pp()
{
    std::cout << "-------------------\n";
    for (int y = 0; y <= 10; ++y)
    {
        for (int x = 0; x <= 10; ++x)
        {
            std::cout << visit[y][x];
        }
        std::cout << '\n';
    }
 
}
 
//정점을 찾아서 리턴함
pos FindVertex(int x, int y, int delta)
{
    while (true)
    {
        pos val = { x, y };
        visit[y][x] = '1';
    
        y += dy[delta];
        x += dx[delta];
        if (arr[y][x] == '0' || y < 1 || 10 < y || x < 1 || 10 < x)
        {
            return val;
        }
    }
}
 
void FindTri()
{
    for (int y = 1; y <= 10; ++y)
    {
        for (int x = 1; x <= 10; ++x)
        {
            if (arr[y][x] == '1')
            {
                tri.push_back({ x, y });
                //dy[8], dx[8]의 8방향 확인
                for (int i = 0; i < 8; ++i)
                {
                    //010
                    //111
                    //같은 상황에서 사용
                    if (arr[y + dy[3]][x + dx[3]] == '1' && arr[y + dy[4]][x + dx[4]] == '1' && arr[y + dy[5]][x + dx[5]] == '1' && i == 4) continue;
                    //111
                    //110
                    //100
                    //같은 상황에서 사용
                    if (arr[y + dy[2]][x + dx[2]] == '1' && arr[y + dy[3]][x + dx[3]] == '1' && arr[y + dy[4]][x + dx[4]] == '1' && i == 3) continue;
                    //아무것도 없는 경우
                    if (arr[y + dy[i]][x + dx[i]] == '0') continue;
 
                    pos tmp = FindVertex(x, y, i);
                    if (tmp.x != x || tmp.y != y)
                    {
                        //찾은 정점이 자기 자신이 아닌경우 정점을 벡터에 추가
                        tri.push_back(tmp);
                    }
 
                }
 
                return;
            }
        }
    }
}
 
//찾은 삼각형 말고 다른 삼각형이 있는지 확인함
bool FindOther()
{
//    std::cout << '\n';
    for (int y = 1; y <= 10; ++y)
    {
        for (int x = 1; x <= 10; ++x)
        {
        //    std::cout << visit[y][x];
            if (visit[y][x] == '1')
            {
                continue;
            }
 
            if (arr[y][x] != '0')
            {
                return true;
            }
        }
    //    std::cout << '\n';
    }
    return false;
}
 
//찾은 삼각형의 내부가 1로 채워져 있는지 확인함, 플러드필처럼 동작함
void IsFilled(pos point)
{
    if (visit[point.y][point.x] == '0' && arr[point.y][point.x] == '1')
    {
        visit[point.y][point.x] = '1';
        for (int i = 0; i < 8; i += 2)
        {
            IsFilled({ point.x + dx[i], point.y + dy[i] });
        }
    }
    else if (visit[point.y][point.x] == '1' && arr[point.y][point.x] == '1')
    {
        return;
    }
    else if (visit[point.y][point.x] == '0' && arr[point.y][point.x] == '0')
    {
        isFilled = false;
    }
}
 
//맨 위 정점(a)에서 뻗어나온 두 정점(b, c)까지의 변 ab, ac와 별개로, 변 bc가 제대로 존재하는지 확인함
bool Fooooooo()
{
    //삼각형이 작아서 확인이 불가능한 경우
    //010 || 11 ||
    //111 || 10 || 등등
    //이러한 경우 참(변 bc가 제대로 존재한다)리턴함
    for (int i = 0; i < 8; ++i)
    {
        if (tri[1].x + dx[i] == tri[2].x && tri[1].y + dy[i] == tri[2].y)
        {
            return true;
        }
    }
    //맨 우측 하단 정점에서 좌측 하단 정점까지 값이 존재하는지 검사함
    pos drawline = { tri[1].x, tri[1].y };
    for (int i = 4; i < 8; ++i)
    {
        if (arr[drawline.y + dy[i]][drawline.x + dx[i]] == '1' && visit[drawline.y + dy[i]][drawline.x + dx[i]] == '0')
        {
            while (drawline.x != tri[2].x || drawline.y != tri[2].y)
            {
                drawline.x += dx[i];
                drawline.y += dy[i];
                //pp();
 
                if (arr[drawline.y][drawline.x] != '1')
                {
                    return false;
                }
                visit[drawline.y][drawline.x] = '1';
            }
            return true;
        }
    }
    return false;
}
 
//0001000000
//0011000000
//0111000000
//1111000000
//0000000000
//0000000000
//0000000000
//0000000000
//0000000000
//0000000000
 
//이등변 삼각형이 맞는지 확인하는 사실상의 메인 함수
bool IsRightTri()
{
    FindTri();
 
    //정점이 3개가 아닌경우 거짓
    if (tri.size() != 3)
    {
        return false;
    }
 
    //변 bc가 존재하지 않는경우 거짓
    if (Fooooooo() == false)
    {
        return false;
    }
 
    //이등변삼각형의 중심(삼각형의 중심 공식 사용)으로부터 삼각형의 내부가 다 채워져있는지 확인
    IsFilled({ (tri[0].x + tri[1].x + tri[2].x) / 3, (tri[0].y + tri[1].y + tri[2].y) / 3 });
    //귀찮아서 전역으로 뺌
    if (isFilled == false)
    {
        return false;
    }
 
    //삼각형 외부에 다른 값이 있는지 확인, 있으면 거짓
    if (FindOther())
    {
        return false;
    }
 
    //정점들의 y값부터 정렬
    std::sort(tri.begin(), tri.end(), cmp);
    //일단 급해서 마구잡이로 코드를 짬
    for (int i = 0; i < 2; ++i)
    {
        //하나의 변이 반드시 수직선과 수평선인 이등변삼각형의 경우 정점 3개의 y와 x값중 반드시 중복되는 값이 나타남.
        int vertexs[3];
        if (i == 0)
        {
            vertexs[0] = tri[0].y;
            vertexs[1] = tri[1].y;
            vertexs[2] = tri[2].y;
        }
        else
        {
            vertexs[0] = tri[0].x;
            vertexs[1] = tri[1].x;
            vertexs[2] = tri[2].x;
        }
 
        std::sort(vertexs, vertexs + 3);
 
        //그를 위해 각각의 값을 정렬, 중복값이 나온다면 이등변 삼각형
        if (vertexs[0] == vertexs[1] || vertexs[1] == vertexs[2])
        {
            return true;
        }
    }
 
    return false;
}
//1110000000
//1100000000
//1000000000
//0000000000
//0000000000
//0000000000
//0000000000
//0000000000
//0000000000
//0000000000
int main()
{
    //삼각형부터 제대로 찾아보자
    for (int y = 1; y <= 10; ++y)
    {
        std::string input;
        std::cin >> input;
        for (int x = 1; x <= 10; ++x)
        {
            arr[y][x] = input[x - 1];
            visit[y][x] = '0';
        }
    }
 
    if (IsRightTri() == false)
    {
        std::cout << 0;
        return 0;
    }
    else
    {
        for (int i = 0; i < 3; ++i)
            std::cout << tri[i].y << ' ' << tri[i].x << '\n';
        return 0;
    }
}
 cs

 

저작자표시

'알고리즘' 카테고리의 다른 글

카카오 2020 5번 - 기둥과 보(구현)  (0) 2020.02.16
카카오 2020 4번 - 가사 검색(트라이)  (0) 2020.02.08
카카오 2020 3번 - 자물쇠와 열쇠(주석미완)  (0) 2020.02.01
백준 2667: 단지번호붙이기 (플러드필, dfs)  (0) 2019.12.15
플로이드 워샬(미완)  (0) 2019.12.15

+ Recent posts

티스토리툴바