[BOJ] 1593 - 문자 해독

https://www.acmicpc.net/problem/1593

1593번: 문자 해독

 

난이도

DFS(X), 투포인터(O) / 난이도 ⭐️⭐️⭐️

 

문제 풀이

투포인터(sliding window)를 써야하는 문제이다. 

 

처음 풀이법은 다음과 같다. 시간 초과난 로직이다.

1) 주어진 단어인 cAda를 활용해 만들 수 있는 모든 단어 조합을 구한다.

2) 단어 조합을 돌면서 문자열 AbrAcadAbRa 에 단어가 포함되어 있는지 검사한다.

 

주어지는 단어는 최대 3000개 알파벳으로 구성될 수 있다.

3000개 알파벳으로 만들 수 있는 길이 3000짜리 모든 단어 조합은?? 

 

+ map 대신에 unordered_map을 사용하니 더 빨라졌다. 

map - 300ms

unrodered_map - 192ms

 

 

맞는 풀이

// https://www.acmicpc.net/problem/1593

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;

int w_cnt, s_cnt;
string w, s;
int result;
bool is_alph_consist_same(unordered_map<char, int> &m1, unordered_map<char, int> &m2)
{
    unordered_map<char, int>::iterator iter;
    int key;
    int value;
    for (iter = m1.begin(); iter != m1.end(); iter++)
    {
        key = iter->first;
        value = iter->second;

        if (m2.find(key) != m2.end())
        { // exist
            if (m2[key] != value)
            {
                return false;
            }
        }
        else
        {
            return false;
        }
    }

    return true;
}

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

    // 1. 입력
    cin >> w_cnt >> s_cnt;
    cin >> w;
    cin >> s;

    // 2. 입력받은 w, s 문자열에 대해 w_cnt만큼 검사하면서 map에 저장
    // w_cnt = 4라면 0~3을 검사하면서 map[알파벳] = 개수 형태로 저장
    unordered_map<char, int> m;
    unordered_map<char, int> m2;

    for (int i = 0; i < w_cnt; i++)
    {
        if (m.find(w[i]) != m.end()) // exist
        {
            m[w[i]]++;
        }
        else
        { // non exist
            m[w[i]] = 1;
        }
    }

    for (int i = 0; i < w_cnt; i++)
    {
        if (m2.find(s[i]) != m2.end()) // exist
        {
            m2[s[i]]++;
        }
        else
        { // non exist
            m2[s[i]] = 1;
        }
    }

    // w, s에 대해 특정 구간안에 포함된 알파벳 구성이 같은지 검사
    if (is_alph_consist_same(m, m2))
        result += 1;

    // 3. 투포인터
    // window를 한칸씩 이동하면서 (0~3 / 1~4 / 2~5) 해당 구간에 포함된 알파벳별 개수를 검사.
    for (int i = w_cnt; i < s.size(); i++)
    {
        if (m2.find(s[i]) != m2.end()) // exist
        {
            m2[s[i]]++;
        }
        else
        { // non exist
            m2[s[i]] = 1;
        }

        m2[s[i - w_cnt]]--;
        //w, s에 대해 특정 구간안에 포함된 알파벳 구성이 같은지 검사
        if (is_alph_consist_same(m, m2))
            result++;
    }

    cout << result;
}

 

틀린 풀이

// https://www.acmicpc.net/problem/1593

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

int w_cnt, s_cnt;
string w, s;
int result;

// substr(시작위치, 갯수);

bool string_include(string word)
{
    int n = word.size();
    bool check = true;
    for (int i = 0; i < s.size() - n; i++)
    {
        check = true;
        for (int j = 0; j < n; j++)
        {
            if (s[i + j] != word[j])
            {
                check = false;
                break;
            }
        }

        if (check)
            return true;
        // if (s.substr(i, n) == word)
        // {
        //     return true;
        // }
    }

    return false;
}

void get_permutaion(string &origin_s, string &new_s, int dest_len, int cur_len)
{
    if (cur_len == dest_len)
    {
        if (string_include(new_s))
        {
            result += 1;
        }
        return;
    }

    char cur_letter;
    for (int i = 0; i < origin_s.size(); i++)
    {
        if (origin_s[i] == '1')
            continue;

        //현재 단어를 선택
        cur_letter = origin_s[i];
        origin_s[i] = '1';
        new_s.push_back(cur_letter);
        get_permutaion(origin_s, new_s, dest_len, cur_len + 1);
        origin_s[i] = cur_letter;
        new_s.pop_back();
    }
}

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

    cin >> w_cnt >> s_cnt;
    cin >> w;
    cin >> s;

    string new_w = "";
    get_permutaion(w, new_w, w_cnt, 0);

    cout << result;
}

심지어 처음에는 substr을 사용했는데, 더 느렸을 것 같다.....(/??????)