< 백준 BaekJoon : 14425번 문자열 집합> C++

<<문제>>

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

14425번: 문자열 집합

 

<<풀이>>

- 집합 s에 n개의 문자를 입력

- m개의 문자를 입력받아 그 중 몇개가  s에 포함되어있는지 찾는 문제

 제가 해결한 방법은 이렇습니다.

 1. n개의 문자열을 집합s(matrixS)에 앞 글자를 기준(a-z:0-25)으로 하여 정리합니다.

2. m개의 문자열을 strInput 변수에 하나씩 입력받아 첫글자가 같은 단어들만 matrixS에서 가지고 나와 비교를 합니다.

 * 이 방법으로 첫 시도에서 시간초과가 걸렸습니다. 아마 길이가 긴 문자열을 비교하는 상황에서 시간을 오래 잡아먹는듯     하여 끝문자를 먼저 비교하여 같은 것들 끼리만 전체 비교를 하여 시간을 줄였습니다.

3. 그렇게 전체 비교를 한 두 문자열이 같으면 결과값 result 변수를 추가합니다.

 

<<코드>>

#include <iostream>
#include <vector>
#include <string>
using namespace std;
/*
 BaekJoon_14425 : 문자열 집합
 집합s에 n개의 문자를 입력시키고 m개의 문자 중 몇개가 포함되어있는지 찾는 문제
 a = 97 z =122
 26개
  입력받은 문자열의 첫글자를 기준으로 vector로 정렬하여 m에서 입력받은 문자열의 앞글자와 같은 문자열들만 비교하도록 하였음
 */

int main() {
    ios_base::sync_with_stdio(false);

    int numN, numM;
    cin >> numN >> numM;
    string strTemp;
    vector<vector<string>> matrixS;
    vector<string> emptyVec;

    for (int i = 0; i < 26; i++) {
        matrixS.push_back(emptyVec);
    }

    for (int i = 0; i < numN; i++) {
        cin >> strTemp;
        matrixS[int(strTemp[0]) - 97].push_back(strTemp);
    }

    int result = 0;
    string strInput;
    int headNum;
    int numTemp;
    for (int i = 0; i < numM; i++) {
        cin >> strInput;
        headNum = int(strInput[0]) - 97;
        numTemp = matrixS[headNum].size();
        if (numTemp != 0) {
            for (int j = 0; j < numTemp; j++) {
                // 시간초과를 해결하기 위해 고안안 방법... 마지막 글자가 같은 경우만 두 문자열을 비교하도록 제한함
                if (matrixS[headNum][j].back() == strInput.back()) { 
                    if (matrixS[headNum][j] == strInput) { result++; }
                }
            }
        }
    }
    cout << result;
}

 

<<깃헙>>

https://github.com/J2on/BaekjoonOnlineJudge/blob/master/V2/BaekJoon_14425.cpp

GitHub - J2on/BaekjoonOnlineJudge: My Study

 

 

더 쉽고 빠르게 풀 수 있을 것 같은 문제인데.. 좋은 방법이 떠오르지 않아 잔꼼수로 해결했네요.