일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 스택
- ROP
- 이분 탐색
- 연결리스트
- 에라토스테네스의 체
- 문자열 처리
- 백트래킹
- 큐
- DFS
- heap
- syscall
- 다이나믹 프로그래밍
- 브루트 포스
- 수학
- OOB
- 투 포인터
- BFS
- BOF
- tcache
- 포맷스트링버그
- 스위핑 알고리즘
- 이진트리
- 동적 계획법
- 완전 탐색
- 이진 탐색
- House of Orange
- fsb
- 분할 정복
- off by one
- RTL
Archives
- Today
- Total
SDJ( 수돈재 아님 ㅎ )
[C++] 1593 - 문자 해독 본문
문제 링크 : https://www.acmicpc.net/problem/1593
1593번: 문자 해독
문제 마야 문자를 해독하는 일은 예상 외로 어려운 일이다. 현재에도 뜻이 완전히 밝혀진 마야 문자는 거의 없는 실정이며, 그나마 해독에 진척이 시작된 지는 30여 년도 되지 않았다. 마야 문자는 소리를 나타내는 여러 종류의 그림글자로 구성되는데, 이 글자들이 여러 위치에서 결합함으로써 단어를 형성한다. 마야 문자 해독을 어렵게 하는 요인 중 하나는 바로 단어를 읽는 순서이다. 마야 문자를 쓰는 고대인들은 단어를 기록할 때 특정한 규칙 대신, 그들이 보기에
www.acmicpc.net
전체 문자열의 길이가 최대 3,000,000이고 알파벳의 개수가 총 26개 이므로
대략 78,000,0000 번 이면 충분히 연산할 수 있지 않을까 라고 생각했다.
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
|
#include<bits/stdc++.h>
using namespace std;
#define endl '\n';
int stan_alpha['z'-'a'+1];
int stan_ALPHA['z'-'a'+1];
int alpha['z'-'a'+1];
int ALPHA['Z'-'A'+1];
int check();
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, s;
string needle;
string hay;
int count = 0;
int start, end;
start = end = 0;
cin >> n >> s;
cin >> needle;
for(int i = 0; i < n; ++i)
{
if('a' <= needle[i] && needle[i] <= 'z')
stan_alpha[needle[i]-'a']+=1;
else
stan_ALPHA[needle[i]-'A']+=1;
}
cin >> hay;
for(end = 0; end < n; ++end)
{
if('a' <= hay[end] && hay[end] <= 'z')
alpha[hay[end] - 'a']+=1;
else
ALPHA[hay[end] - 'A']+=1;
}
count += check();
while(end < s)
{
if('a' <= hay[start] && hay[start] <= 'z')
alpha[hay[start] - 'a']-=1;
else
ALPHA[hay[start] - 'A']-=1;
start += 1;
if('a' <= hay[end] && hay[end] <= 'z')
alpha[hay[end] - 'a'] += 1;
else
ALPHA[hay[end] - 'A'] += 1;
end += 1;
count += check();
}
cout << count;
return 0;
}
int check()
{
for(int i = 0; i < 'z'-'a'+1; ++i)
{
if(stan_ALPHA[i] != ALPHA[i])
return 0;
if(stan_alpha[i] != alpha[i])
return 0;
}
return 1;
}
|
'알고리즘 > Backjoon' 카테고리의 다른 글
[C++] 9421 - 소수상근수 (0) | 2020.01.20 |
---|---|
[C++] 2606 - 바이러스 (0) | 2020.01.20 |
[C++] 7576 - 토마토 (0) | 2020.01.20 |
[C++] 1260 - DFS와 BFS (0) | 2020.01.20 |
[C++] Mini Sudoku X (0) | 2020.01.20 |