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

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

작성자:

0. 문제

3986번: 좋은 단어

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;
}
Code language: PHP (php)

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

  • 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;
}
Code language: PHP (php)
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;
            }
        }
Code language: PHP (php)

같지만 더 편한 방법이다.

Featured image for [C++] call by value? reference?
[C++] call by value? reference?
1. 주소연산자&와 참조연산자& #include using namespace std; int value(int a){ a += 10; cout << "value : " << a << " "; return 0; } int ref(int& a){ //참조연산자& a += 10; cout << "ref : " << a << " "; return 0; } int main(){ int a = 1; value(a); cout << a << '\n'; ref(a); cout << a << '\n'; return 0; } /* value : 11 1 ref : 11 11 */ int ref(int& a){ //참조연산자&: & 기호는 C++에서 참조를 의미합니다. 참조는 변수의 별명(alias)으로 볼 수 있으며, 그 변수가 저장된 메모리 주소에 직접 접근할 수 … 더 읽기
// 백준 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;
}
Code language: PHP (php)

조금 고쳐도 안된다.

다. 수정

“같은 글자가 연속되면 지운다. 이를 반복해서 모든 글자가 지워지면 좋은 글자다.”라는 조건 만족하는지 알기 위해서 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());
Code language: JavaScript (javascript)

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

// 백준 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;
}
Code language: PHP (php)

허무하다…

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

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

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

+23년 9월 3일 추가

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

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

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

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

댓글 남기기