Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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
- Union-find
- 소감
- 카카오
- 투포인터
- 알고리즘
- IBK기업은행 #기업은행 #디지털 #직무 #정리
- 백준
- BaekJoon
- 중반부
- 코테
- BFS
- c++
- 보석쇼핑
- 삼성 #코테 #2020상반기 #c++
- 카카오인턴
- 식단
- Algorithm
- 1편
- 스마일게이트
- 서버개발캠프
- 유니온파인드
- LIS #Algorithm #요소추적
- Smilegate
- 코딩테스트
Archives
- Today
- Total
짱아의 개발 기록장
백준 1593번. 문자 해독(c++) / 문자열 처리 본문
반응형
생각보다 까다로웠던 문제?
시간초과와 틀렸습니다 늪에 빠져 푸는 데에 오래걸렸다....
sliding window문제!!
그냥 해독하려는 문자열을 기준으로 찾고자 하는 단어의 크기만큼 (g만큼) 길이를 잡아서
w문자열과 종류가 같고 개수도 같은지 확인하면 된다.
나는 map을 사용하여 종류와 개수를 판단했다.
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
|
// 문자해독 (sliding window)
#include <map>
#include <iostream>
using namespace std;
int n, m;
string w, s;
map<char, int> origin; // w문자열에서의 구성글자
map<char, int> tmp; // s문자열에서의 구성글자(w문자열의 길이만큼 슬라이딩 윈도우로 계산)
int kind = 0; // w문자열의 종류
int num = 0; // s문자열의 종류(w문자열의 길이만큼 슬라이딩 윈도우로 계산)
int ans = 0;
int main()
{
cin>>n>>m;
cin>>w>>s;
for(int i=0; i<n; i++){
if(origin.count(w[i])==0){
origin[w[i]] = 1;
kind++;
}else{
origin[w[i]]++;
}
}
int Start = 0;
int End = n-1;
// s문자열에서 처음 n개의 문자에 대해 계산
for(int i=0; i<n; i++){
if(tmp.count(s[i])==0){
tmp[s[i]] = 1;
num++;
}else{
tmp[s[i]]++;
}
}
while(1)
{
if(num==kind){
bool check = true;
for(int i=Start; i<=End; i++){
if(tmp[s[i]]!=origin[s[i]]){
check = false;
break;
}
}
if(check) ans++;
}
// Start값 조정
if(tmp[s[Start]]==1){
tmp.erase(s[Start]);
num--;
}else{
tmp[s[Start]]--;
}
Start++;
// End값 조정
End++;
if(End>=m) break;
if(tmp.count(s[End])==0){
tmp[s[End]] = 1;
num++;
}else{
tmp[s[End]]++;
}
}
cout<<ans<<"\n";
return 0;
}
|
cs |
문제 첨부
https://www.acmicpc.net/problem/1593
1593번: 문자 해독
문제 마야 문자를 해독하는 일은 예상 외로 어려운 일이다. 현재에도 뜻이 완전히 밝혀진 마야 문자는 거의 없는 실정이며, 그나마 해독에 진척이 시작된 지는 30여 년도 되지 않았다. 마야 문자�
www.acmicpc.net
반응형
'Algorithm > Baekjoon' 카테고리의 다른 글
백준 16924번. 십자가 찾기(c++) / 시뮬레이션 (0) | 2020.07.29 |
---|---|
백준 1701번. Cubeditor(c++) / kmp (0) | 2020.07.27 |
백준 17398번. 통신망 분할(c++) / union-find (0) | 2020.07.23 |
백준 1890번. 점프(c++) / DP (0) | 2020.07.22 |
백준 16472번. 고냥이(c++) / 투포인터 (0) | 2020.07.22 |
Comments