[알고리즘] 3986번: 좋은 단어

0. 문제

 

3986번: 좋은 단어

 

---

1. 문제 이해

예제 입력 1

3
ABAB
AABB
ABBA

예제 출력 1

2

예제 입력 2

3
AAA
AA
AB

예제 출력 2

1

 

1. 단어의 길이가 홀수면 무조건 나쁜 단어다.
2. 사용된 A와 B의 개수도 짝수여야 한다.
3. A든 B든 첫 번째 글자로 단어를 잘랐을 때 모든 조각은 1번과 2번을 만족해야 한다. → split 활용하기

 

---

2. 제출

 

가. 틀렸습니다.

// 백준 3986번: 좋은 단어
#include <iostream>
#include <vector>

using namespace std;

int n, ret;

bool isOdd(string str){
    return (str.length() & 1);
}

int cntChar(string str, char c){
    int cnt = 0;
    for(char i : str)
        if(i==c) cnt++;
    return cnt;
}

vector<string> splitMethod(string input, string delimiter){
    vector<string> splited;
    auto pos = 0;
    string token ="";
    while((pos = input.find(delimiter)) != string::npos){
        token = input.substr(0,pos);
        if(token!="")splited.push_back(token);
        input.erase(0, pos+delimiter.length());
    }
    if(token!="")splited.push_back(token);
    return splited;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n;
    for(int i=0; i<n; i++){
        string word;
        cin >> word;
        if(isOdd(word)) continue;
        if(cntChar(word, 'A') & 1)continue;

        string deli = "";
        vector<string> v = splitMethod(word, (deli=word[0]));
        bool check = true;
        for(string str : v){
            if(isOdd(str)){
                check = false;
                break;
            }
        }
        if(check) ret++;
        v.clear();
    }
    cout << ret << "\n";
    return 0;
}

좋은 단어의 조건을 잘못 파악했다.

• AABBBAAB같은 경우 오답이 발생한다.

 

처음부터 계속 시간초과를 당하니깐 시간을 줄이는 것에 너무 신경 쓴 것 같다.

 

우선 돌아가도록 만드는 것이 더 중요한 것 같다.

 

---

나. 시간 초과

 

1. 단어의 길이가 홀수면 무조건 나쁜 단어다.
2. 사용된 A와 B의 개수도 짝수여야 한다.
3. 같은 글자가 연속되면 지운다. 이를 반복해서 모든 글자가 지워지면 좋은 글자다.

 

// 백준 3986번: 좋은 단어
#include <iostream>
#include <vector>

using namespace std;

int n, ret;

bool isOdd(string str){
    return (str.length() & 1);
}

int cntChar(string str, char c){
    int cnt = 0;
    for(char i : str)
        if(i==c) cnt++;
    return cnt;
}

bool check(string* str){   // 추가
    for(int i=0; i<str->length()-1; i++){
        if((*str)[i] == (*str)[i+1]){
            str->erase(i, 2);
            return false;
        }
    }
    return true;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n;
    for(int i=0; i<n; i++){
        string word;
        cin >> word;
        if(isOdd(word)) continue;
        if(cntChar(word, 'A') & 1)continue;

        while(true){   // 수정
            if(check(&word)) break;
            if(word.length()==0){
                ret++; break;
            }
        }
    }
    cout << ret << "\n";
    return 0;
}

 

bool check(string& str){   // 추가
    for(int i=0; i<str.length()-1; i++){
        if(str[i] == str[i+1]){
            str.erase(i, 2);
            return false;
        }
    }
    return true;
}

...

        while(true){
            if(check(word)) break; //&word -> word
            if(word.length()==0){
                ret++; break;
            }
        }

같지만 더 편한 방법이다.

 

 

[C++] call by value? reference?

 

// 백준 3986번: 좋은 단어
#include <iostream>
#include <vector>

using namespace std;

int n, ret;

bool isOdd(string str){
    return (str.length() & 1);
}

int cntChar(string str, char c){
    int cnt = 0;
    for(char i : str)
        if(i==c) cnt++;
    return cnt;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n;
    for(int i=0; i<n; i++){
        string word;
        cin >> word;
        if(isOdd(word)) continue;
        if(cntChar(word, 'A') & 1)continue;



    }
    cout << ret << "\n";
    return 0;
}

조금 고쳐도 안된다.

 

---

다. 수정

 

“같은 글자가 연속되면 지운다. 이를 반복해서 모든 글자가 지워지면 좋은 글자다.”라는 조건 만족하는지 알기 위해서 string을 순회하면서 같은 글자가 연속되면 지우는 코드를 사용했다.

 

bool check = false;
do{
    for(int j=0; j<word.length()-1; j++){
        if(word[j] == word[j+1]){
            word.erase(j, 2);
            check = true;
            j--;
        }
        if(!word.length()){
            ret++;
            break;
        }
    }
}while(check && word.length());

이와 같이 반복문을 이중으로 사용하기보다 “스택”을 사용하면 더 쉽고 빠르게 구현할 수 있다.

 

// 백준 3986번: 좋은 단어
#include <iostream>
#include <stack>

using namespace std;

int n, ret;

/*
bool isOdd(string str){
    return (str.length() & 1);
}

int cntChar(string str, char c){
    int cnt = 0;
    for(char i : str)
        if(i==c) cnt++;
    return cnt;
}
*/

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n;
    for(int i=0; i<n; i++){
        string word;
        cin >> word;
        //if(isOdd(word)) continue;
        //if(cntChar(word, 'A') & 1)continue;

        stack<char> stk;   // 수정
        for(char a : word){
            if(stk.size() && stk.top() == a)stk.pop(); // 스택의 참조 에러와 언더플로우 조심!
            else stk.push(a);
        }
        if(stk.size() == 0)ret++;
    }
    cout << ret << "\n";
    return 0;
}

 

허무하다…

 

하나의 문제 A를 풀기 위해서 다른 문제 A2를, A2를 풀기 위해서 A3를, A3를 풀기 위해서 … 우선적으로 다른 문제를 풀어야 하는 상황이다.

 

미해결 문제가 쌓이고 언제 해결할 수 있을지는 알 수 없다.

 

이때 이중 반복문을 사용하면 일방통행이라면, 스택을 사용하면 양방향으로 효율적으로 왔다 갔다 하면서 문제를 풀 수 있다.

 

---

+23년 9월 3일 추가

 

위와 같은 것을 Divide & Conquer라고 한다.

 

분할 정복 알고리즘(Divide and conquer algorithm)은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘이다.

 

• 분할 정복 알고리즘은 보통 재귀 함수(recursive function)를 통해 자연스럽게 구현된다.
• 빠른 실행이나 부문제 해결 순서 선택을 위해, 재귀호출을 사용하지 않고 스택, 큐(queue) 등의 자료구조를 이용하여 분할 정복법을 구현하는 것도 가능하다.

 

출처 : https://ko.wikipedia.org/wiki/분할_정복_알고리즘

---