일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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
- OOB
- 문자열 처리
- 에라토스테네스의 체
- House of Orange
- ROP
- 동적 계획법
- syscall
- 브루트 포스
- 포맷스트링버그
- fsb
- 스택
- 큐
- RTL
- 완전 탐색
- 이진트리
- 백트래킹
- off by one
- DFS
- heap
- 다이나믹 프로그래밍
- BFS
- tcache
- BOF
- 투 포인터
- 수학
- 이진 탐색
- 스위핑 알고리즘
- 연결리스트
- 분할 정복
- 이분 탐색
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 |
Comments