Codeforces Round #806 (Div. 4) - D

문제 출처:

https://codeforces.com/contest/1703/problem/D

 

문제 분석:

입력 받은 String이 나머지 String들 중 두개를 뽑아서 만들 수 있는지 없는지를 체크하는 문제이다.

 

문제 해결:

처음에 String을 모두 set에 삽입시켜놓고

확인할 String을 각 자릿수 별로 두개로 나눈다.

ex) abcd
a + bcd
ab + cd
abc + d

그리고 나뉜 각 부분을 set에서 찾으면 되는 문제이다.

 

내 소스코드:

// freopen("input.txt", "r", stdin);
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#include <string>
#include <queue>
#include <stack>
#include <cstring>
#include <list>
#include <set>
#include <string.h>
#include <map>
#include <limits.h>
#include <stdlib.h>
#include <typeinfo>
#include <bitset>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define F first
#define S second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int INF = 987654321;

int testcase;

string arr[100002];

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

    cin >> testcase;

    while (testcase--)
    {
        int n;
        cin >> n;

        set<string> ms;

        for (int i = 0; i < n; i++)
        {
            string tmp;
            cin >> tmp;
            arr[i] = tmp;
            ms.insert(tmp);
        }
        string ans = "";
        for (int i = 0; i < n; i++)
        {
            bool check = false;
            string cur = arr[i];
            string tmp1;
            string tmp2;
            for (int j = 1; j < cur.size(); j++)
            {
                if (check)
                    break;
                tmp1 = cur.substr(0, j);
                tmp2 = cur.substr(j , cur.size() - j);

                if (ms.find(tmp1) != ms.end() && ms.find(tmp2) != ms.end())
                {
                    ans += "1";
                    check = true;
                }
            }
            if (!check)
                ans += "0";
        }
        cout << ans << "\n";
    }


    return 0;
}

 

고찰 :

생각을 잘못해서 처음부터 나눈것이아니라

각 문자열 별로 순회하면서 있으면 나눈 것이 시간을 많이 잡아먹고 틀린 결과를 가져왔다.

순회 했을때 문자열의 중간에 껴져있는경우

틀렸습니다 오류를 내뱉는다.