[프로그래머스][level3] 브라이언의 고민 (C++)

https://programmers.co.kr/learn/courses/30/lessons/1830

코딩테스트 연습 - 브라이언의 고민

 

 

[난이도] level3
[유형] 구현

[풀이]
규칙1을 만족하는 모든 부분문자열을 찾고 규칙2를 만족하는 모든 부분문자열을 찾는 방식으로
문자열을 여기저기 뒤지면서 찾는 방법으로 접근했다가 풀이에 실패했던 문제입니다.

위와 같이 풀게 되면 예외 케이스도 너무 많이 생기게 되고 원본 문자열을 복구하는데도 어려움이 있습니다.

더 쉬운 방법은 index 0부터 시작하는 valid한 부분문자열 떼어내기를 반복하며, 만약 0부터 시작해서 valid한 부분문자열이 없다면 invalid를 return해주는 방식입니다.

항상 0번 문자을 포함하는 valid한 부분문자열을 구하면 됩니다.

0번 문자 sentence[0]이 소문자인 경우와 대문자인 경우로 나눠주고 시작합니다.

i) sentence[0]이 소문자인 경우
rule2가 적용되어야 합니다. aXXXXa 혹은 aBcBcBa와 같은 두가지 형태가 있을 수 있습니다.

    1) vector에 sentence[0]이랑 같은 문자를 가지고 있는 index들을 저장합니다.
    2) vector의 크기는 반드시 2여야 합니다. 아니면 invalid를 return합니다.
    3) vector의 두 index 사이의 문자열이 aXXXXa,aBcBcBa 둘중 한가지 형태가 맞는지 확인해야 합니다.
       이를 위해 rule1 함수와 allUpper 함수를 정의하였습니다.

       (※문제의 지문에서 규칙2를 적용한 것이지만 코드를 작성하다보니 함수명을 rule1로 하였습니다.)
       rule1 함수는 전달된 string이 rule2의 형태 (BcBcB) 인지 확인해서 맞으면 원본 string(BBB) 를 return하고
       아닌 경우 "-1"을 return합니다.
       주의할 점이 (B) 형태는 rule1을 만족하지 않아야 합니다. 저는 소문자 포함유무를 ok flag를 통해 체크해서 걸러냈         습니다.

       allUpper 함수는 전달된 string이 (XXXX) 형태인지를 체크합니다.

       먼저 rule1인지 체크하고 "-1"을 return 했다면 allUpper를 체크합니다 이것도 역시 "-1"이라면
       invalid한것이므로 "invalid"를 최종 return합니다.

       rule1 혹은 allUpper를 만족했다면 return된 string을 answer에 추가해주고
       sentence에서 확인 부분까지 제거하고 다음 시행으로 넘어갑니다.

       이때 소문자는 한번밖에 사용 못하는 규칙이 있기 때문에 used[26] vector에 소문자를 사용할때마다 소문자를 사용 했는지를 체크해줘야 합니다.

 

ii) sentence[0]이 대문자인 경우

    ii-1) AAAAx...와 같이 sentence[1]도 대문자인 경우
        sentence[0]은 무조건 떼어내서 answer에 추가해주고
        다음 시행으로 넘어가면 됩니다. 원본 문자에 공백이 있었다고 가정하면 되기 때문에 붙어있는 대문자들은 한개씩
        떼어낼 수 있습니다.

    ii-2) AbB...와 같이 sentence[1]이 소문자인 경우
        sentence[1]과 같은 모든 index들을 vector에 담아준 뒤 이것의 개수에 따라 다르게 처리해줍니다.

        ii-2-1) vector의 크기가 2가 아닌 경우
            크기가 1인 경우 AbB, 3이상인 경우 AbBbBbBbC 형태일수밖에 없으므로 위에서 사용한 

            rule1을 만족하는지 체크합니다.
            만족하면 answer에 추가하고 다음 시행으로 넘어갑니다.

        ii-2-2) vector의 크기가 2인 경우
            AbBbA 형태이거나, AbBBBBBBbC 형태일 수 있습니다.
            AbBbA도 A bBb A 형태로 쪼개면 후자의 형태와 같이 볼 수 있고,
            후자의 형태로 최대한 자르는 것이 더 유리합니다.

            그러므로 sentence[0]만 잘라서 answer에 추가해주고 다음 시행으로 넘어갑니다.
            이러면 자연스럽게 sentence[1]은 소문자였으므로 i)케이스 가게 됩니다.

위의 과정을 sentence가 empty가 될때까지 반복하면 최종 답을 얻을 수 있습니다.

 

 

#include <string>
#include <cctype>
#include <vector>
#include <iostream>
using namespace std;
const string ivd = "invalid";
string rule1(string str){
    string ret;
    if(str.size()<3) return "-1";
    char c = str[1];
    bool ok=0;
    for(int i=0;i<str.size();i++){
        if(islower(str[i])) ok=1;
        if(i%2==0){
            if(islower(str[i])) return "-1";
            ret+=str[i];
        }else{
            if(c!=str[i]) return "-1";
        }
    }
    if(!ok) return "-1";
    return ret;
}
string allUpper(string str){
    string ret;
    for(auto c : str){
        if(!isupper(c)) return "-1";
        ret+=c;
    }
    return ret;
}
string solution(string sentence) {
    vector<bool> used(26,0);
    string answer = "";
    int it=0;
    while(!sentence.empty()){
        string ret;
        vector<int> pos;
        if(islower(sentence[0])){
            if(used[sentence[0]-'a']) return ivd;
            used[sentence[0]-'a']=1;
            for(int i=0;i<sentence.size();i++){
                if(sentence[i]==sentence[0]) {
                    pos.push_back(i);
                }
            }
            if(pos.size()!=2) return ivd;

            string center = sentence.substr(1,pos.back()-1);
            if(center=="") return ivd;
            ret = rule1(center);
            string target;
            if(ret=="-1") {
                ret=allUpper(center);
                if(ret=="-1"){
                    return ivd;
                }
            }else{
                if(used[sentence[2]-'a']) return ivd;
                used[sentence[2]-'a']=1;
            }
            sentence = sentence.substr(pos.back()+1);
        }else{
            if(sentence.size()==1 || isupper(sentence[1])){
                ret=sentence[0];
                sentence=sentence.substr(1);
            }else{
                for(int i=0;i<sentence.size();i++){
                    if(sentence[1]==sentence[i]) pos.push_back(i); 
                }

                if(pos.size()!=2){
                    if(pos.back()==sentence.size()-1) return ivd;
                    if(islower(sentence[pos.back()+1])) return ivd;
                    string center = sentence.substr(0,pos.back()+2);
                    ret=rule1(center);
                    if(ret=="-1") return ivd;
                    if(used[sentence[1]-'a']) return ivd;
                    used[sentence[1]-'a']=1;
                    sentence=sentence.substr(pos.back()+2);
                }else{
                    ret=sentence[0];
                    sentence=sentence.substr(1);
                }   
            }
        }
        answer+=ret+" ";
    }
    answer.pop_back();
    return answer;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/브라이언의_고민.cpp