22.06.06. 풀었던 문제들

4시간동안 고민했던 브라이언의 고민... 이런 고민은 좀 하지 마라..

​

1. 브라이언의 고민

너무너무 어렵게 풀었다.

처음 접근은 'rule 2가 적용된 모든 것들을 풀고, 이후에 rule 1이 적용되어 있는 것을 풀어야지' 했는데 이것저것 반례가 계속 튀어나와 덕지덕지 테이프칠하다 보니 너무 더러워져서 다시 깔끔하게 풀기로 했다.

먼저. 어떤 s[i]를 봤을 때 2가지 경우의 수가 있다.

1) 대문자 - rule 1이 적용되었거나, 아무것도 적용되지 않은 경우

- 따라서 다음 글자가 대문자이면 s[i]를 정답 vector에 붙여넣는다.

- 다음 글자가 소문자이면 해당 소문자의 개수가 2가 아니라면 rule 1을 적용한다. (2라면 rule 2를 적용시킬 것임)

2) 소문자 - rule 2가 적용되었거나, rule2와 rule1 둘 다 적용된 경우

- 따라서 rule2를 풀어야 한다.

추가적으로 사용한 소문자의 경우 isused로 계속 체크해 주어야 한다.

#include <string>
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>

using namespace std;
struct chardata{
    int start, end, num;
    char c;
};

bool isAllUpper(string& sentence, int startidx, int endidx){
    for(int i = startidx; i<=endidx; i++){
        if(!isupper(sentence[i])) return false;
    }
    return true;
}

string getRule1(string& sentence, chardata& cd){
    // 아래 것 때문에 오류가 있었다. Aa와 같은 경우에는 A는 빠지고 a만 남는데, a 양쪽에 아무것도 없는 경우에도 ""를 리턴하기 때문에 예외처리.
    if(cd.end + 1 >= sentence.size() || cd.start - 1 < 0) return "invalid";
    for(int j = cd.start; j<=cd.end; j += 2){
        if(isupper(sentence[j]) || sentence[j] != cd.c) return "invalid";
    }
    string result = "";
    for(int j = cd.start-1; j<=cd.end+1; j += 2){
        if(islower(sentence[j])) return "invalid";
        result += sentence.substr(j, 1);
    }
    if(result == "") return "invalid";
    return result;
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
string solution(string sentence) {
    unordered_map<char, chardata> m;
    for(int i = 0; i<sentence.size(); i++){
        char c = sentence[i];
        if(isupper(c)) continue;
        if(m.find(c) == m.end()){
            chardata cd; cd.start = cd.end = i; cd.num = 1; cd.c = c;
            m[c] = cd;
        }
        else{
            m[c].end = i; m[c].num++;
        }
    }
    
    vector<string> answer_v;
    map<char, int> used;
    for(int i = 0; i<sentence.size(); i++){
        if(isupper(sentence[i])){ // 대문자이면
            if(i+1 < sentence.size() && islower(sentence[i+1]) && m[sentence[i+1]].num != 2){
                // 다음 글자가 소문자이고 소문자 개수가 2가 아니라면 rule1이 적용된 것. rule1을 푼다.
                chardata cd = m[sentence[i+1]];
                if(used[cd.c] == 1) return "invalid";
                used[cd.c] = 1;
                string result = getRule1(sentence, cd);
                if(result == "invalid") return result;
                answer_v.push_back(result);
                i = cd.end+1;
            }
            else{ // 아니라면 해당 대문자는 분리해서 정답 vector에 push
                answer_v.push_back(sentence.substr(i, 1));
            }
        }
        else{ // 소문자이면 무조건 rule2가 적용된 것. rule2를 푼다.
            chardata cd = m[sentence[i]];
            if(used[cd.c] == 1) return "invalid";
            used[cd.c] = 1;
            if(cd.num != 2) return "invalid"; // rule2가 적용되지 않았다면 invalid
            if(isAllUpper(sentence, cd.start+1, cd.end-1)){ // 내부가 모두 대문자이면 그것을 리턴.
                string result = sentence.substr(cd.start+1, cd.end - cd.start - 1); 
                if(result == "") return "invalid"; // 만약 비었다면 invalid
                answer_v.push_back(result);
            } else{ // rule2와 rule1이 둘 다 적용되었다면
                if(i+2 < sentence.size() && !islower(sentence[i+2])) return "invalid";
                chardata nestedcd = m[sentence[i+2]];
                if(used[nestedcd.c] == 1) return "invalid";
                used[nestedcd.c] = 1;
                string result = getRule1(sentence, nestedcd); // rule1을 푼다.
                if(result == "invalid") return result;
                answer_v.push_back(result);
            }
            i = cd.end;
        }
    }
    
    
    
    string answer = "";
    for(string s : answer_v){
        answer += s + " ";
    }
    return answer.substr(0, answer.length()-1);
}