[백준] 11059 크리 문자열 c++
11059. 크리 문자열
https://www.acmicpc.net/problem/11059
11059번: 크리 문자열
첫째 줄에 문자열 S가 주어진다. S는 숫자로만 이루어져 있으며, 길이는 1,000을 넘지 않는다. 항상 크리 문자열이 존재하는 입력만 주어진다.
www.acmicpc.net
입력의 길이는 1000을 넘지 않는다. 입력의 길이가 굉장히 큰 것은 아니기때문에 부담을 갖지 않아도 될 것 같다.
크리 문자열이 무엇일까?
대칭되는 짝수 길이의 문자열을 의미하는 것인가? (처음 필자는 대칭되는 것만 말하는 줄 알았다..ㅎ;ㅎ;;;;)
대칭이 안되어도 합만 같으면 된다!!
int main() {
ios::sync_with_stdio(0);
cout.tie(); cin.tie();
cin >> s;
for (int i = 0; i < s.size(); i++) {
for (int j = 1;j+i < s.size(); j += 2) {
check(i, j);
}
}
cout << temp;
}코드를 먼저 살펴보며 설명하는 것이 쉬운 문제인 것 같다. 우선 check()함수는 크리 문자열인지 확인해 주는 함수이다.
check 함수로 보내게될 짝수길이의 s의 부분 문자열의 인덱스를 이중for문을 통하여 표현했다.
부분 문자열의 시작인덱스를 i 그리고 j는 i로부터 짝수 길이의 문자열을 구하기 위하여 1,3,5,.... 씩 더해준다.
(즉, i는 시작 인덱스 j는 길이를 나타낸다. --> ((실제 길이-1)이다.... 저렇게 설정한 이유는.... 실수이다 ㅎㅎ....ㅎ)
void check(int st, int ed) {
sum_front = 0;
sum_back = 0;
for (int k = st; k <= st+((ed + 1) / 2) - 1; k++) {
sum_front += s[k];
}
for (int k = st+(ed + 1) / 2; k <= st + ed; k++) {
sum_back += s[k];
}
if (sum_front == sum_back) {
temp = max(temp, ed + 1);
}
return;
}check함수를 살펴보자. 크리 문자열을 어떻게 판달할까?
앞 절반의 합은 sum_front에 저장하고 뒤 절반의 합은 sum_back에 저장했다.
전달된 부분 문자열의 첫번째 인덱스~앞 절반까지의 숫자를 모두 더해주었고, 앞절반+1~끝까지의 숫자를 모두 더해주었다. 그리고 그 값이 같다면 합을 temp에 저장해줬다.
temp의 경우는 크리 문자가 발견될 때마다 더 큰 값이 발견된다면 max()함수를 통하여 업데이트 해준다.
코드:
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
string s;
int sum_front = 0;
int sum_back = 0;
int temp = 0;
void check(int st, int ed) {
sum_front = 0;
sum_back = 0;
for (int k = st; k <= st+((ed + 1) / 2) - 1; k++) {
sum_front += s[k];
}
for (int k = st+(ed + 1) / 2; k <= st + ed; k++) {
sum_back += s[k];
}
if (sum_front == sum_back) {
temp = max(temp, ed + 1);
}
return;
}
int main() {
ios::sync_with_stdio(0);
cout.tie(); cin.tie();
cin >> s;
for (int i = 0; i < s.size(); i++) {
for (int j = 1;j+i < s.size(); j += 2) {
check(i, j);
}
}
cout << temp;
}