문제 URL : https://www.acmicpc.net/problem/5525
5525번: IOIOI
N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇
www.acmicpc.net
문제접근법 :
부분 문자열의 개수를 구하는문제인데
문제가 친절하게도 n의 개수만큼 O가 존재하고 반드시 양옆에 I가존재해야합니다.
즉 I가 먼저나오고 그다음 O가 그다음 I로 끝나야하는건 누구나알죠
그럼 어떻게 알까?
저는 deque를 이용했습니다.
????
어떻게 deque를 이용했을까?
우선 처음 I가 발견된다면 그녀석은 부분문자열일 가능성을 갖은놈이죠
그럼 deque에 뒤로 집어넣습니다.
그다음 반드시 O를 넣어야하고 O라면 deque가 맨뒤에데이터가 반드시 I어야 하겠죠?
만약 비어있거나 I라면 deque는 반드시 들어있던 모든데이터를 지워주고 I를 하나 넣어줍니다. 왜냐
II같은 연속적으로 2번이상 나온문자열일수도 존재하니까 마지막I부터 다시 체크해줘야합니다.
그리고 다시 I를 집어넣을때 뒤에 있는것이 O라는것만 알면되기때문에 이것들만
반복하면됩니다.
그리고deque의 사이즈가 n*2+1 일때 부분문자열이고
맨앞의 deque의 데이터를 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
|
#include<bits/stdc++.h>
using namespace std;
int n, m;
string s;
void input() {
cin >> n >> m;
cin >> s;
}
void solve() {
int cnt = 0;
int size = 2 * n + 1;
deque<char> dq;
for (char c : s) {
if (c == 'I') {
if (dq.empty() || dq.back() == 'O')
dq.push_back(c);
else {
dq.clear();
dq.push_back(c);
}
}
else {
if (!dq.empty() && dq.back() == 'I')
dq.push_back(c);
else
dq.clear();
}
if (!dq.empty() && dq.front() == 'I')
if (dq.size() == size) {
cnt++;
dq.pop_front();
dq.pop_front();
}
}
cout << cnt << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
input();
solve();
}
|
cs |
궁금한점 혹은 모르는점 어떤질문이든 댓글은 언제나 환영입니다.
'백준' 카테고리의 다른 글
| 백준 15480 LCA와 쿼리 (0) | 2023.01.18 |
|---|---|
| 백준 14676 영우는 사기꾼? (0) | 2022.11.15 |
| 백준 1007 벡터 매칭 (1) | 2022.11.01 |
| 백준 피보나치 수 6 (0) | 2022.10.20 |
| 백준 15730 수영장 사장님 (1) | 2022.08.04 |
