ML/AI/SW Developer

SWEA-12222 문자열 나누기(C++, Python)

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 문제로서 모든 조합을 검사하지 않고, 앞에서 부터 차례대로 패턴을 만들어가며 검사를 진행한다.