글 읽기 - 어디서 틀렸을까요?

playsworld16 2년 전 0

제가 생각한 풀이는 다음과 같습니다.

문자열 s에 대해

1. s의 길이가 2 이하일 경우 한가지 알파벳으로만 이루어져있으니 그대로 답에 추가합니다.

2.1 s가 a?a?a?a...a?a 형식으로 되있을 경우 a를 빼내 답에 추가합니다. 나머지 문자열로 solve 함수를 재귀호출합니다.

2.2 아닌 경우 a가 앞에서 짝수개로 연속되어 있다는 뜻이므로 (예: aabaacaabaa, aaaabaaaa) 연속된 부분을 빼내 답에 추가합니다. 나머지 문자열로 solve 함수를 재귀호출합니다.

어디서 틀린걸까요?

#include <bits/stdc++.h>
using namespace std;

string S;
vector<int> A;

void solve(string s){
    int n = s.size();
    
    if (n <= 2){
        S += s[0];
        A.push_back(n);
        return;
    }
    
    // 홀수 개 테스트
    bool ok = (n%2==1);
    for (int i = 2; i < n; i+=2){
        if (s[i] != s[i-2]) ok = 0;
    }
    
    if (ok){
        S += s[0];
        A.push_back(1);
        
        string ns;
        for (int i = 1; i < n; i+=2) ns += s[i];
        solve(ns);
        return;
    }
    
    // 앞에 붙어있는 연속된 알파벳을 추출
    int idx = 1;
    while(idx < n && s[idx] == s[idx-1]) idx++;
    
    S += s[0];
    A.push_back(idx);
    
    string ns;
    for(int i = idx; i < n; i += idx+1){
        ns += s[i];
    }
    solve(ns);
}

int main(){
    
    string s;
    cin >> s;
    solve(s);
    
    cout << S << '\n';
    for(auto k : A) cout << k << ' ';
}

kdh6429 2년 전 1

빈 문자열을 재귀호출하는 경우가 있습니다. 아래 참고하세요.

입력

abacabaaabacabaaabacabaaabacabaaabacabaaabacabaaabacabaaabacabaaabacabaaabacaba

출력

1 1 1 1 4 0

정답

1 1 1 1 4

playsworld16 2년 전 0

생각지도 못한 부분이었네요. 감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어디서 틀렸을까요?

playsworld16 2년 전 0

kdh6429 2년 전 1

playsworld16 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말