[프로그래머스/C++] 브라이언의 고민 (2017 카카오코드 예선)

문제

문제 설명

 

 

풀이

 

 

이 문제는 많은 예외처리를 하느라 시간이 꽤 걸린 문제였다

반례도 많이 만들어 테스트를 했다...

 

[문제 풀이]

 

이 문제에서 중요하게 봐야할 점들은 아래와 같다.

 

1. 광고 규칙은 2개가 있으며, 서로 다른 광고 규칙 2개는 같이 적용될 수 있다.

2. 하나의 광고규칙이 한 단어에 여러번 적용될 수는 없다.

3. 광고 규칙에 사용된 소문자는 다시 사용할 수 없다.

 

위 3가지 사항에 유의해서 문제를 풀어야 한다.

 

먼저 광고문구 sentence를 앞에서부터 탐색한다.

이때, 대문자가 나오면 tempString이라는 str에 더한다.

 

만약 소문자가 나오면 그 소문자가 sentence에 몇 개가 나오는지 센다.

 

여기서 소문자의 개수에 따라 광고 규칙 1인지 2인지 구분할 수 있다.

 

1. 소문자의 개수가 1인 경우

 

이 경우는 무조건 광고 규칙 1을 따라야한다. (광고 규칙2는 무조건 소문자가 2개가 나와야 하기 때문)

그러므로 소문자가 1개가 나오면 이때 소문자 양옆의 문자가 한 단어가 된다.

여기서 중요한 점은 왼쪽에 나온 대문자가 다른 규칙에 의해 포함된 단어인지 검사해야한다.

 

다른 규칙에 의해 포함된 단어인지 검사하는 방법은 여러개가 있지만, 나는 어떤 index까지 단어에 포함했는지 체크하는 방법을 사용했다.

 

+ 일단 추가하고 최종적으로 return할 string과 sentence의 대문자 수를 비교해 검증하는 방법도 있다.

 

2. 소문자의 개수가 3인 경우

 

이 경우도 무조건 광고 규칙 1을 따라야한다. 

 

아래와 같은 문장이 있다고 예를 들어 보자

여기서 소문자 a가 처음 등장한 i번 index부터 마지막으로 같은 소문자가 나온 index까지 2칸 간격으로 소문자 a가 나와야한다.

그리고 i-1번 인덱스부터 2칸 간격의 문자들을 전부 더하면서 마지막 인덱스인 i+7번째 문자까지 단어를 만든다.

만들어진 단어인 BBBBC를 추가하면 된다.

 

여기서 만약 BBBBC에 소문자가 있다면 규칙에 위반된 것이므로, invalid를 return 하면된다.

 

3. 소문자의 개수가 2개인 경우

 

이 경우는 규칙 1번을 따를수도 있고, 2번을 따를 수도 있다.

여기서 1번 규칙보다 2번 규칙을 따른다고 일단 가정하는게 광고 문구를 제거하는데 효과적이다.

 

아래 그림을 통해 이유를 알아보자.

 

위 4가지 경우를 살펴보면 소문자가 2개인 경우에 1번 경우는 1번 규칙과 2번 규칙을 전부 적용할 수 있다.

하지만 나머지 2, 3, 4번의 경우에는 무조건 2번 규칙을 따라야 한다.

 

그러므로 소문자가 2개가 나올 경우 2번 규칙을 따르는게 유리하다.

 

이제 2번 규칙을 적용하기 전에, 1번 규칙도 같이 적용되어 있는지 체크를 해야한다.

 

만약 1번 규칙이 같이 적용되어 있다면, 문자 사이에 다른 소문자가 무조건 1개 존재한다.

그러므로 문자 안에 다른 소문자가 존재한다면, 무조건 1번 규칙과 2번 규칙이 같이 적용돼 있다.

 

이후에 1번 규칙에 맞게 적용되어 있는지 검사하면 된다.

 

검사하는 방법은 이전과 마찬가지로 2칸 간격으로 체크를 하면 된다.

 

이후 위 과정으로 문자를 체크하고 나면, set에 소문자를 넣어 이미 사용한 소문자임을 체크해주면 된다.

 

그리고 다음으로 탐색하는 문자는 현재 소문자가 나온 마지막 index 이후부터 탐색하면 된다. 

(그 사이에 있는 문자는 전부 탐색을 완료하고 추가했으므로 넘어갈 수 있다.)

 

+

테스트에 사용했던 반례

 

​

[아이디어 정리]

1. 광고문구를 탐색하며 소문자가 발견되면 그 소문자가 광고문구에 총 몇 개 있는지 체크한다.
2. 소문자의 개수가 2개라면 2번 규칙, 2개가 아니라면 1번 규칙을 따른다.
3. 규칙에 따라 단어를 추가한다.
4. 만약 2번 규칙이라면 그 사이에 1번 규칙이 같이 적용되어 있는지 검사한다.
5. 규칙에 따라 광고문구를 제거해 추가한 단어가 전부 대문자인지 검사한다.

 

 

Code

 

 

#include <string>
#include <vector>
#include <set>
using namespace std;

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
string solution(string sentence) {
    vector<string> aaa;
    string answer = "";
    char nowAlpha=sentence[0];
    int ttt=nowAlpha-'a';
    int prevCheckIdx=-1;
    string tempString="";
    set<char> finalCheck;
    // 예외 처리
    if (ttt>=0&&ttt<26)// 소문자
    {
        int tempCnt=0;
        for (int i=0; i<sentence.length(); i++)
        {
            if (nowAlpha==sentence[i])
            {
                tempCnt+=1;
            }
        }    
        if (tempCnt!=2)
            return "invalid";
    }
    
    for (int i=0; i<sentence.length(); i++)
    {
        nowAlpha=sentence[i];
        ttt=nowAlpha-'a';
        if (ttt>=0&&ttt<26)// 소문자
        {
            int nowAlphaCnt=0;
            char tempAlpha, tempAlpha2;
            int lastIdx=0;
            for (int j=i; j<sentence.length(); j++)
            {
                tempAlpha=sentence[j];
                if (tempAlpha==nowAlpha)
                {
                    nowAlphaCnt+=1;
                    lastIdx=j;
                }                
            }
            if (nowAlphaCnt==1) //규칙1
            {
                if (finalCheck.find(nowAlpha)!=finalCheck.end())
                {
                    return "invalid";
                }
                else
                {
                    finalCheck.insert(nowAlpha);
                }
                if (i-1<=prevCheckIdx)
                {
                    return "invalid";
                }
                if (i-1<0||i+1>=sentence.length())
                {
                    return "invalid";
                }
                else
                {
                    tempString=tempString.substr(0,tempString.length()-1);
                    if (tempString!="")
                    {
                        aaa.push_back(tempString);                     
                    }
                    tempString="";
                    tempString+=sentence[i-1];
                    tempString+=sentence[i+1];
                    aaa.push_back(tempString);
                    tempString="";
                }
                i+=1;
                prevCheckIdx=lastIdx+1;
            }
            else if (nowAlphaCnt==2) //규칙2라고 생각하기
            {
                // 규칙1,2가 같이 있는지 검사
                if (finalCheck.find(nowAlpha)!=finalCheck.end())
                {
                    return "invalid";
                }
                else
                {
                    finalCheck.insert(nowAlpha);
                }
                if (tempString!="")
                {
                    aaa.push_back(tempString);    
                }
                int ttt2;
                tempString="";
                bool flag=false;
                for (int j=i+1; j<lastIdx; j++)
                {
                    tempAlpha2=sentence[j];
                    ttt2=tempAlpha2-'a';
                    if (ttt2>=0&&ttt2<26)// 소문자
                    {
                        flag=true;
                        break;
                    }
                    else
                    {
                        tempString+=tempAlpha2;
                    }                
                }
                if (flag)
                {
                    tempString="";
                    char sameC=sentence[i+2];
                    if (finalCheck.find(sameC)!=finalCheck.end())
                    {
                        return "invalid";
                    }
                    else
                    {
                        finalCheck.insert(sameC);
                    }
                    for (int j=i+2; j<lastIdx; j+=2) // 겹쳐있다면, i+2는 전부 소문자이며 같은 문자다.
                    {
                        tempAlpha2=sentence[j];
                        if (sameC!=tempAlpha2)
                        {
                            return "invalid";
                        }
                    }
                    for (int j=i+1; j<=lastIdx; j+=2) // 겹쳐있다면, i+2는 전부 소문자이며 같은 문자다.
                    {
                        tempString+=sentence[j];
                    }
                    if (tempString=="")
                    {
                        return "invalid";
                    }
                    aaa.push_back(tempString);
                    tempString="";
                }
                else
                {
                    if (tempString=="")
                    {
                        return "invalid";                        
                    }
                    aaa.push_back(tempString);
                    tempString="";
                }
                i=lastIdx;
            }
            else //규칙 무조건 1, 3개이상이므로
            {
                if (finalCheck.find(nowAlpha)!=finalCheck.end())
                {
                    return "invalid";
                }
                else
                {
                    finalCheck.insert(nowAlpha);
                }
                tempString=tempString.substr(0,tempString.length()-1);
                if (tempString!="")
                {
                    aaa.push_back(tempString);
                    tempString="";
                }
                if (i-1<=prevCheckIdx)
                {
                    return "invalid";
                }
                char sameC=sentence[i];
                for (int j=i; j<=lastIdx; j+=2) // i+2는 전부 소문자이며 같은 문자다.
                {
                    tempAlpha2=sentence[j];
                    if (sameC!=tempAlpha2)
                    {
                        return "invalid";                        
                    }
                }
                if (lastIdx+1>=sentence.length())
                {
                    return "invalid";
                }
                for (int j=i-1; j<=lastIdx+1; j+=2) // i+2는 전부 소문자이며 같은 문자다.
                {
                    tempString+=sentence[j];
                }
                prevCheckIdx=lastIdx+1;
                aaa.push_back(tempString);
                tempString="";
                i=lastIdx+1;
            }
        }
        else
        {
            tempString+=nowAlpha;
        }
    }
    if (tempString!="")
    {
        aaa.push_back(tempString);        
    }
    for (int j=0; j<aaa[0].length(); j++)
    {
        ttt=aaa[0][j]-'a';
        if (ttt>=0&&ttt<26)// 소문자가 들어가면 불가능
        {
            return "invalid";
        }
    }
    answer=aaa[0];
    for (int i=1; i<aaa.size(); i++)
    {
        for (int j=0; j<aaa[i].length(); j++)
        {
            ttt=aaa[i][j]-'a';
            if (ttt>=0&&ttt<26)// 소문자가 들어가면 불가능
            {
                return "invalid";
            }
        }
        answer+=" "+aaa[i];
    }
    
    return answer;
}

 

---

 

이 문제는 거의 처음 프로그래머스를 풀 때 봤었다.

코드를 작성해봤지만, 구현이 오래 걸릴 것 같아서 나중에 풀어야겠다고 생각하고 넘어간 문제였다.

역시나 예상했던 대로 반례가 너무 많아서 푸는데 생각보다 오래 걸렸다...

 

그리고 드디어 프로그래머스의 문제들 중 C++로 풀 수 있는 Lv.3 문제와 Lv.4 문제를 전부 풀었다!!

 

당분간은 프로그래머스에서 정답률이 낮은 Lv.2 또는 백준 문제를 풀어야겠네...

아니면 Lv.5 를 풀어야되나?

 

프로그래머스