문제 URL : https://www.acmicpc.net/problem/1013
1013번: Contact
입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 전파를 표현하는, { 0, 1 }만으로 이루어진 문자열이 공백 없이 주어진다. 문자열 길이는 (1 ≤
www.acmicpc.net
접근법 :
사실 이문제 2년전에 풀었지만 regex를 이용하는 문제가아닌 오토마타를 이용해서 DFA를 그려가며
풀었던문제인데 정규표현식 공부중이라 정규표현으로 풀었고
정규표현식이 얼마나 깔끔하고 편한지 깨닫게 되더군요
작년엔 정말 어렵게풀었는데 정규표현식으로 답을 제출했을땐 말잇못...ㅋㅋㅋㅋ
소스코드 :
정규표현식 소스코드
|
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
|
#include <bits/stdc++.h>
using namespace std;
int n;
vector<string> v;
void input() {
cin >> n;
v.resize(n);
for (int i = 0; i < n; i++)
cin >> v[i];
}
void solve() {
for (int i = 0; i < n; i++) {
cout << (regex_match(v[i], regex("(100+1+|01)+"))?"YES":"NO") << "\n";
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
input();
solve();
}
|
cs |
코드가 너무 깔끔해서 할말이 없습니다. 시간도 빠르고
DFS를 그려가며 작성했던 코드
|
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
|
#include <iostream>
#include <string>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
bool check(string s)
{
int state='a';
for(int i=0;i<s.size();i++)
{
switch(state)
{
case 'a':
if(s[i]=='0')
state='f';
else
state='b';
break;
case 'b':
if(s[i]=='0')
state='c';
else
return false;
break;
case 'c':
if(s[i]=='0')
state='d';
else
return false;
break;
case 'd':
if(s[i]=='0')
state='d';
else
state='e';
break;
case 'e':
if(s[i]=='0')
state='f';
else
state='h';
break;
case 'f':
if(s[i]=='0')
return false;
else
state='g';
break;
case 'g':
if(s[i]=='0')
state='f';
else
state='b';
break;
case 'h':
if(s[i]=='0')
{
if(i+1<s.size())
{
if(s[i+1]=='0')
{
state='c';
}
else
{
state='f';
}
}
else
return false;
}
else
state='h';
}
}
return state=='e'||state=='h'||state=='g';
}
int main()
{
int test;
cin>>test;
string s;
while(test--)
{
cin>>s;
if(check(s))
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
}
|
cs |
1년전이라 되있지만 2019년에 풀었더군요 그때와 지금 코드 스타일이 정말많이 변했네요 거기다가
노가다했던 보람이 무색하게도 노가다코드가 더느리고 regex의 유용함을 알게되어 좀더 발전할수 있을것같네요
궁금한점 혹은 모르는점 언제든지 어떤질문이든 댓글을 달아주시면 환영입니다.
'백준' 카테고리의 다른 글
| 백준 1520 내리막 길 (0) | 2021.07.26 |
|---|---|
| 백준 2671 잠수함식별 (0) | 2021.07.26 |
| 백준 3447 버그왕 (0) | 2021.07.23 |
| 백준 9996 한국이 그리울 땐 서버에 접속하지 (0) | 2021.07.23 |
| 백준 1916 최소비용 구하기 (0) | 2021.07.23 |
