문제 URL : https://www.acmicpc.net/problem/14426
14426번: 접두사 찾기
문자열 S의 접두사란 S의 가장 앞에서부터 부분 문자열을 의미한다. 예를 들어, S = "codeplus"의 접두사는 "code", "co", "codepl", "codeplus"가 있고, "plus", "s", "cude", "crud"는 접두사가 아니다. 총 N개의 문자
www.acmicpc.net
문제접근법 :
두가지 풀이를 얘기 해드릴게요
한가지는 무식하게 모든 접두사를 다만들어서 set에 저장합니다
abcde 의 접두사라면
a
ab
abc
abcd
abcde
이렇게 모든 접두사를 전부 저장하여 그접두사가 있는지 확인하는 접근하여 풀수있습니다.
하지만 시간과 공간복잡도는 n^2이 나오기때문에 효율적으로는 떨어지지만 정답은 맞출수 있습니다.
2번째는
이분탐색을 이용한 코드이빈다.
입력받은 string을 정렬한후
이분탐색을 이용한후 찾고자하는 s2의 길이만큼 자른후 같은지 확인해서 판단하면 끝입니다.
소스코드:
첫뻔재 풀이:
|
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
|
//By 콩순이냉장고
#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
int n, m;
unordered_set<string> pset;
void input() {
cin >> n >> m;
string s;
for (int i = 0; i < n; i++) {
cin >> s;
string s2;
for (int i = 0; i < s.size(); i++) {
s2 += s[i];
pset.insert(s2);
}
}
}
void solve() {
int res = 0;
for (int i = 0; i < m; i++) {
string s;
cin >> s;
if (pset.find(s) != pset.end())
res++;
}
cout << res << "\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
input();
solve();
}
|
cs |
2번째 소스코드
|
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
|
//By 콩순이냉장고
#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
int n, m;
vector<string> v;
void input() {
cin >> n >> m;
string s;
for (int i = 0; i < n; i++) {
cin >> s;
v.push_back(s);
}
}
void solve() {
int res = 0;
sort(v.begin(), v.end());
for (int i = 0; i < m; i++) {
string s;
cin >> s;
int l = 0, r = n - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (s < v[mid]) {
r = mid - 1;
}
else if (s > v[mid]) {
l = mid + 1;
}
if (v[mid].substr(0,s.size()) == s) {
res++;
break;
}
}
}
cout << res << "\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
input();
solve();
}
|
cs |
궁금한점 혹은 모르는점 언제든지 댓글은 언제나 환영입니다.
'백준' 카테고리의 다른 글
| 백준 9996 한국이 그리울 땐 서버에 접속하지 (0) | 2021.07.23 |
|---|---|
| 백준 1916 최소비용 구하기 (0) | 2021.07.23 |
| 백준 12904 A와 B (0) | 2021.07.15 |
| 백준 16934 게임 닉네임 (0) | 2021.07.11 |
| 백준 17609 회문 (0) | 2021.07.05 |
