1. 문제 설명
- 문제 링크
- 알파벳 소문자로 이루어진 문자열 S
- 조건을 만족하는 최대 K 찾기
- 단 $S_i와 S_{i+1}$ 은 달라야한다.
- E.g. aabbaa -> {a, b, ba, a} 로 4
- 15개의 테스트 케이스를 합쳐서 13초
- $1 <= S길이 <= 2*10^5$
2. 풀이
- 모든 단어를 끊었을때 최대의 길이가 될 수있다.
- 즉, $문자열_i$ 와 $문자열_{i+1}$ 이 다르다면 나누는 것이 좋다
- Cur과 pre를 이용해 접근 가능
- Cur을 빈문자열 부터 하나씩 늘려가며 pre와 다르면 answer에 추가!
- 인접한 문자열만 다르면 되고, 최대로 만들어야 하기 때문에 짧게 할 수록 유리하다.
3. 코드
- c++
// 테스트용 함수
void Print(vector<string>& strs) {
for (int i = 0; i < strs.size(); i++) {
cout << strs[i] << endl;
}
}
int main(int argc, char** argv)
{
int test_case;
int T;
cin >> T;
for (test_case = 1; test_case <= T; ++test_case)
{
// 데이터 입력 받기
string str;
cin >> str;
vector<string> ans;
// 문자열 길이 만큼 반복 검사!
int answer = 0; // S 개수
string cur = ""; // 현재 부분문자열 S_i
string pre = ""; // 이전 부분문자열 S_{i-1}
for (int i = 0; i < str.length(); i++) {
cur += str[i];
if (cur != pre) {
// 테스트용
ans.push_back(cur);
answer++; //pre와 다르니까 추가가능
pre = cur; // pre cur로 변경
cur = ""; // cur 초기화
}
}
cout << "#" << test_case << " " << answer << endl;
// 테스트용
Print(ans);
}
return 0;//정상종료시 반드시 0을 리턴해야합니다.
}
- python
# 알고리즘은 C++과 동일
T = int(input())
for test_case in range(1, T + 1):
S = str(input())
answer = 0
cur = ""
pre = ""
for idx in range(S.length()):
cur = cur + S[idx]
if cur != pre:
answer += 1
pre = cur
cur = ""
print("#{0} {1}".format(test_case, answer))
4. 결과
확실히 문자열을 다루는 기능은 python이 c++에 비해 압도적인것 같다.
굉장히 긴 문자열도 입력으로 주어지기 때문에, 한번 순회로 답을 찾아내는 것이 포인트라고 생각했다. 그리고, 모든 단어를 끊었을 때 최대 길이가 되기 때문에 항상 끊으려고 노력하는 것이 좋다는 것을 생각하고, 사용가능 한 패턴이 나오면 바로 답에 넣어주고 초기화 해주면 되겠다는 생각을 바로 할 수 있었다. greedy가 어려운 편이었는데, 이번 문제는 풀이법이 바로 떠올랐다.
greedy 문제로서 모든 조합을 검사하지 않고, 앞에서 부터 차례대로 패턴을 만들어가며 검사를 진행한다.