ALGOSPOT WILDCARD

2020.02.17

WILDCARD

풀이

• 기본적으로 input1, input2를 입력받으면서 바로 비교하도록 함수를 구현하였고 비교해서 조건을 만족하면 결과 벡터에 푸시하였다. 마지막으로 compare와 함께 결과를 sort 해서 출력하였다.
• *, ?, 문자 경우를 나누어 재귀함수를 이용해 idx1,idx2를 증가, 그대로 두며 완전탐색하도록 만들었다.
• 동적계획법 문제인데 먼저 완전탐색으로 확인하여 시간초과가 나면 DP를 어떻게 적용할지 고려해보려 했는데 시간초과없이 통과해버렸다..

코드

//! 2020.02.17
// TODO AS_WILDCARD
// Brute Force (Dynamic Programming)
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

int C, N;
vector <string> result;
int sizeStr;
string input1;
string input2;

bool compare(string s1, string s2) {
    if (s1.compare(s2) < 0) return true;
    else return false;
}

bool getResult(int idx1,int idx2) {
    if (idx1 >= input1.length()) {
        if(idx2 >= input2.length()) return true;
        else return false;
    }
    else {
        if (input1[idx1] == '*'){
            if (idx2 >= input2.length()) return getResult(idx1+1,idx2);
            else return getResult(idx1 + 1, idx2 + 1) || getResult(idx1, idx2 + 1) || getResult(idx1 + 1, idx2);
        }
        else{
            if (idx2 >= input2.length()) return false;
            else if (input1[idx1] == '?') return getResult(idx1 + 1, idx2 + 1);
            else if (input1[idx1] == input2[idx2]) return getResult(idx1 + 1, idx2 + 1);
            else return false;
        }
    }
}

int main() {
    cin >> C;
    for (int c = 0; c < C; c++) {
        cin >> input1;
        cin >> N;
        for (int n = 0; n < N; n++) {
            cin >> input2;
            //cout << input1 << endl << input2 << endl;
            if (getResult(0,0)) result.push_back(input2);
        }
        //printf("%d\n", result[0].compare(result[1]));
        sort(result.begin(), result.end(), compare);
        //cout << "my results!!!" << endl;
        for (int i = 0; i < result.size(); i++) {
            cout << result[i] << endl;
        }
        vector <string> empty;
        result.swap(empty);
    }

    return 0;
}

실수

* 일때 idx2 를 증가시키거나 idx1와 함께 증가시키거나 두가지 경우만 탐색했었다. 하지만 idx1만 증가하는 경우도 있었고 이를 고려해서 해결하였다.

메모이제이션 활용

idx1, idx2를 각각 증가시키면서 매칭을 시도할 때, *로 인해 결국 idx1부터 끝까지, idx2부터 끝까지를 재귀함수가 비교하게 된다.

이 때, 한번 구했던 결과는 다른 * 혹은 다른 문자에서 비교한다고 해도 같은 결과다.

결국 같은 비교를 여러번 하게 된다는 의미이다.

즉, 알고리즘 상 O(N^2) 으로 비교할 수 있는 데, 여러번 반복하기 때문에 *의 갯수만큼 더 비교하게 되고 최악의 경우 O(N^3)에 가깝게 시간복잡도가 늘어날 수 있다.

메모이제이션을 통해 이를 막을 수 있었고, 196ms 를 4ms로 줄일 수 있었다.

코드

//! 2020.02.17
// TODO AS_WILDCARD
// Brute Force (Dynamic Programming)
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

const int MAX = 105;
int C, N;
vector <string> result;
int sizeStr;
string input1;
string input2;
int DP[MAX][MAX];

bool compare(string s1, string s2) {
    if (s1.compare(s2) < 0) return true;
    else return false;
}

bool getResult(int idx1, int idx2) {
    int& ret = DP[idx1][idx2];
    if (ret != -1) return ret;
    if (idx1 >= input1.length()) {
        if (idx2 >= input2.length()) return ret = 1;
        else return ret = 0;
    }
    else {
        if (input1[idx1] == '*') {
            if (idx2 >= input2.length()) return ret = getResult(idx1 + 1, idx2);
            else return ret = getResult(idx1 + 1, idx2 + 1) || getResult(idx1, idx2 + 1) || getResult(idx1 + 1, idx2)? 1:0;
        }
        else {
            if (idx2 >= input2.length()) return ret = 0;
            else if (input1[idx1] == '?') return ret = getResult(idx1 + 1, idx2 + 1);
            else if (input1[idx1] == input2[idx2]) return ret = getResult(idx1 + 1, idx2 + 1);
            else return ret = 0;
        }
    }
}

void resetDP(int rows, int cols) {
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            DP[i][j] = -1;
        }
    }
}

int main() {
    resetDP(MAX, MAX);
    cin >> C;
    for (int c = 0; c < C; c++) {
        cin >> input1;
        cin >> N;
        for (int n = 0; n < N; n++) {
            cin >> input2;
            //cout << input1 << endl << input2 << endl;
            if (getResult(0, 0)==1) result.push_back(input2);
            resetDP(input1.length()+1, input2.length()+1);
        }
        //printf("%d\n", result[0].compare(result[1]));
        sort(result.begin(), result.end(), compare);
        //cout << "my results!!!" << endl;
        for (int i = 0; i < result.size(); i++) {
            cout << result[i] << endl;
        }
        vector <string> empty;
        result.swap(empty);
    }

    return 0;
}