개발 블로그

문제 링크 : https://www.acmicpc.net/problem/16171

문제

친구가 적은 성민이는 수업에 결석해도 시험이나 과제에 대한 정보를 제대로 얻을 수 없었다. F 학점을 받을 위기까지 아슬아슬하게 결석일 수를 유지하던 성민이는, 어느 날 갑자기 영문도 모른 채 쪽지시험을 보게 되었다!

갑작스러운 쪽지 시험으로 마음이 급해진 성민이는 매직아이를 사용해 벼락치기를 하기로 한다.

성민이가 듣는 과목의 교과서는, 알파벳 소문자(a-z)와 알파벳 대문자(A-Z)로만 이루어져 있다. 성민이가 교과서에서 찾고자 하는 키워드도 역시 알파벳 소문자와 대문자로만 이루어져 있다. 하지만, 성민이에겐 큰 문제가 생겼다. 결석한 날의 수업 내용을 친구에게 빌려 필기를 하던 중, 교과서에 숫자(0-9)를 적어버린 것이다.

키워드를 찾기 힘들어 패닉에 빠진 성민이는 몇 안 되는 친구인 당신에게 도움을 요청했다. 성민이를 도와, 교과서에서 성민이가 찾고자 하는 키워드의 존재 여부를 알려주자.

입력

첫 번째 줄에는 알파벳 소문자, 대문자, 숫자로 이루어진 문자열 S가 주어진다. (1 ≤ |S| ≤ 100) 두 번째 줄에는 성민이가 찾고자 하는 알파벳 소문자, 대문자로만 이루어진 키워드 문자열 K가 주어진다. (1 ≤ |K| ≤ 100).

단, 입력으로 들어오는 키워드 문자열 K의 길이는, 교과서의 문자열 S보다 짧거나 같다.

출력

첫 번째 줄에 성민이가 찾고자 하는 키워드가 문자열 내에 존재하면 1, 존재하지 않으면 0을 출력한다.

접근 방법

입력 받은 문자열을 하나씩 따져가면서 해당 문자에서 '0'을 빼서 int 형으로 바꿔본다.

바꾼 수가 0~9 사이이면 패스하고, 아니라면 string removedNum에 해당 문자를 붙인다.

removedStr.find()를 사용해서 부분 문자열의 포함 여부를 알 수 있다. 

참고로 포함 되었을 때 find()는 removedStr 중 부분 문자열이 포함된 첫 인덱스를 리턴한다.

ex)

removedStr = "abbc";

string s = "bb"

int result = removedStr.find(s);    //result = 1

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

int main(){
    
    string str, str2; 
    cin >> str >> str2;

    string removedStr = "";
    for(int i = 0; i<str.length(); i++){
        if(str[i] -'0' >= 0 && str[i] - '0' <=9) continue;
        removedStr.push_back(str[i]);
    }

    if(removedStr.find(str2) == string::npos){  //없으면
        cout << 0;
    }else cout << 1;


    return 0;
}

문제 링크 : https://www.acmicpc.net/problem/20154

문제

가톨릭대학교에 다니는 컴퓨터정보공학부 황톨릭은 코로나 때문에 슬퍼하는 친구들을 위해 게임을 하나 만들었다.

게임이 시작되면 알파벳 대문자로만 이루어진 문자열이 주어진다. 문자열이 주어지면 각 문자의 획수로 문자를 변환한다. 획수들을 갖고 앞에서부터 두 개씩 더해가는데 만약 짝이 지어지지 않는다면 그대로 다음 단계로 내려간다. 다음 단계부터는 이전 단계에서 두 개씩 더해가며 생성된 숫자들을 가지고 같은 과정을 반복한다. 과정을 반복하다가 결국 마지막 한 개의 수가 남았을 때 그 수가 홀수라면 이기는 것이고 짝수라면 지는 게임이다!!

예를 들어 "ABCDE"라는 문자열이 주어지면 ‘A’, ‘B’, ‘C’, ‘D’, ‘E’ 각 문자의 획수인 3, 2, 1, 2, 3으로 바꾸어 아래의 그림처럼 과정을 진행한다. 단, 계산할 때, 더한 값이 10을 넘는다면 10으로 나눈 나머지로 바꿔준다.

‘E’의 경우는 짝을 지을 수 없으므로 3이 바로 내려오게 된다. 결국, 마지막 남은 수가 1인 홀수이므로 이 게임은 이기게 되는 것이다.

게임의 심판역할인 톨릭이는 매번 계산하는 게 귀찮아 코드를 짜놓고 싶어한다. 톨릭이를 도와 코드를 짜주자!!

알파벳 대문자의 획수는 아래 표와 같다.

접근 방법

계산의 편의를 위해서 int, string, char를 적절하게 변환해야 하는 문제였다.

char -> int  : char에 '0'을 빼주면된다.
int or char -> string  : to_string()를 쓰면 된다.

알고리즘은 아래 단계와 같다.

1) 획수를 alpha[] 에 차례로 저장한다.

2) 입력 문자열에 대한 획수를 alpha[]에서 구한 다음, 그 획수를 string 형으로 바꿔서 쭉 붙이고 cntStr에 저장한다. 즉, 입력문자열이 "ABCDE" 면 cntStr는 "32123"이 저장된다.

3) cntStr의 길이가 1이 될 때까지 while문을 반복한다.

    3)-1. 획수가 쭉 이어져 있는 문자열인 cntStr를 따라가면서 짝지어서 획수를 더해서 계산한다.

    3)-2. 그 계산 값을 문자열 tmp에 'push_back()함수' 또는 '+=' 연산을 이용해서 붙여준다. 

    3)-3. 짝이 안 맞는 수가 하나 남으면 마지막에 tmp에 그대로 이어 붙여준다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;

int alpha[26] = {3,2,1,2,3,3,3,3,1,1,3,1,3,3,1,2,2,2,1,2,1,1,2,2,2,1};
int main(){
    
    string str; cin >> str;

    string cntStr = "";
    for(int i = 0; i<str.length(); i++){
        cntStr += to_string(alpha[str[i]-65]);
    }   

    while(cntStr.length()>1){
        int len = cntStr.length();
        if(len == 1) break;

        string tmp = "";
        if(len % 2 != 0)
        { //짝 안 맞는게 하나 있을 때
            for(int i = 0; i<len-1; i+=2){  
                int num = ((cntStr[i]-'0') + (cntStr[i+1]-'0'))%10;
                tmp += to_string(num);
                
            }
            tmp.push_back(cntStr[len-1]);
            cntStr = tmp;
        }
        else
        { //모두 짝이 맞을 때
            for(int i = 0; i<len; i+=2){   
                int num = ((cntStr[i] - '0') + (cntStr[i + 1] - '0')) % 10;
                tmp += to_string(num);
            }
            cntStr = tmp;
        }
    }

    int res = cntStr[0] - '0';
    if(res % 2 != 0) {
        cout << "I'm a winner!";
    }
    else{
        cout << "You're the winner?";
    }



    return 0;
}

문제 링크 : https://www.acmicpc.net/problem/10798

문제

아직 글을 모르는 영석이가 벽에 걸린 칠판에 자석이 붙어있는 글자들을 붙이는 장난감을 가지고 놀고 있다. 

이 장난감에 있는 글자들은 영어 대문자 ‘A’부터 ‘Z’, 영어 소문자 ‘a’부터 ‘z’, 숫자 ‘0’부터 ‘9’이다. 영석이는 칠판에 글자들을 수평으로 일렬로 붙여서 단어를 만든다. 다시 그 아래쪽에 글자들을 붙여서 또 다른 단어를 만든다. 이런 식으로 다섯 개의 단어를 만든다. 아래 그림 1은 영석이가 칠판에 붙여 만든 단어들의 예이다. 

A A B C D D a f z z 0 9 1 2 1 a 8 E W g 6 P 5 h 3 k x

<그림 1>

한 줄의 단어는 글자들을 빈칸 없이 연속으로 나열해서 최대 15개의 글자들로 이루어진다. 또한 만들어진 다섯 개의 단어들의 글자 개수는 서로 다를 수 있다. 

심심해진 영석이는 칠판에 만들어진 다섯 개의 단어를 세로로 읽으려 한다. 세로로 읽을 때, 각 단어의 첫 번째 글자들을 위에서 아래로 세로로 읽는다. 다음에 두 번째 글자들을 세로로 읽는다. 이런 식으로 왼쪽에서 오른쪽으로 한 자리씩 이동 하면서 동일한 자리의 글자들을 세로로 읽어 나간다. 위의 그림 1의 다섯 번째 자리를 보면 두 번째 줄의 다섯 번째 자리의 글자는 없다. 이런 경우처럼 세로로 읽을 때 해당 자리의 글자가 없으면, 읽지 않고 그 다음 글자를 계속 읽는다. 그림 1의 다섯 번째 자리를 세로로 읽으면 D1gk로 읽는다. 

그림 1에서 영석이가 세로로 읽은 순서대로 글자들을 공백 없이 출력하면 다음과 같다:

Aa0aPAf985Bz1EhCz2W3D1gkD6x

칠판에 붙여진 단어들이 주어질 때, 영석이가 세로로 읽은 순서대로 글자들을 출력하는 프로그램을 작성하시오.

입력

총 다섯줄의 입력이 주어진다. 각 줄에는 최소 1개, 최대 15개의 글자들이 빈칸 없이 연속으로 주어진다. 주어지는 글자는 영어 대문자 ‘A’부터 ‘Z’, 영어 소문자 ‘a’부터 ‘z’, 숫자 ‘0’부터 ‘9’ 중 하나이다. 각 줄의 시작과 마지막에 빈칸은 없다.

출력

영석이가 세로로 읽은 순서대로 글자들을 출력한다. 이때, 글자들을 공백 없이 연속해서 출력한다. 

접근 방법

브론즈 1단계 문제로 간단하게 해결할 수 있다.

배열 크기의 최대값인 [5][15]만큼 '.'로 초기화 한뒤, 5개의 문자열을 입력받는다.

입력을 다 한 후 세로로 읽다가 '.'이 나오면 해당 칸은 글자가 없는 것을 의미하므로 continue로 건너 뛰고 다음 행의 문자를 탐색한다.

'.'가 아니면 push_back() 를 이용하여 정답 문자열에 해당 문자를 추가한다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;

char arr[5][15];
int main(){

    string str = "";
    string answer = "";

    for (int r = 0; r < 5; r++)
    {
        for (int c = 0; c < 15; c++)
        {
            arr[r][c] = '.';
        }
    }

    for(int i = 0; i<5; i++){
        cin >> str;
        for(int j = 0; j<str.length(); j++){
            arr[i][j] = str[j];
        }
    }
    
    
    for(int c = 0; c<15; c++){
        for (int r = 0; r < 5; r++)
        {
            if (arr[r][c] == '.') continue;
            answer.push_back(arr[r][c]);
                
        }
    }

    cout << answer;

    return 0;
}

문제 링크 : https://www.acmicpc.net/problem/9046

문제

암호학에서 치환 암호(substitution cipher)란, 평문에 들어있는 각각의 문자를 주어진 치환 방법으로 암호화하는 방법 중 하나다.

가장 단순한 방법은 평문의 알파벳을 암호문의 알파벳으로 대치시켜 치환시키는 것이다.

예를 들어, 아래와 같은 알파벳 대치표가 주어졌다고 하자.

• 평문 알파벳 대치표 : abcdefghijklmnopqrstuvwxyz
• 암호문 알파벳 대치표 : wghuvijxpqrstacdebfklmnoyz

위에 주어진 치환 방법을 통해 암호화하면 평문 "hello there"은 "xvssc kxvbv"가 된다.

한 가지 흥미로운 점은 영어 문법 특성상, 알파벳 'e'가 다른 영문 알파벳에 비해 자주 쓰인다는 것이다.

즉, 암호문 알파벳 대치표 없이 암호문을 복호화하려 할 때, 암호문 알파벳 빈도수를 체크하면 암호문 알파벳 빈도수 중 가장 빈번하게 나타나는 알파벳이 'e'라는 사실을 유추해볼 수 있다.

위 방법으로 암호문 알파벳의 빈도수를 체크하고, 가장 빈번하게 나타나는 문자를 출력하는 프로그램을 작성하면 된다.

만약 주어진 암호문에서 가장 빈번하게 나타나는 문자가 여러 개일 경우, 그 빈번한 문자 중 어느 것이 평문 알파벳 'e'를 가리키는지 확실하게 알 수 없기 때문에 "모르겠음"을 의미하는 '?'를 출력하면 된다.

입력

입력의 T(1 ≤ T ≤ 20)는 테스트 케이스로, 입력 제일 상단에 주어진다. 각각의 테스트 케이스는 한 줄마다 소문자와 공백으로 이루어진 영어 문장이 주어진다. 이 문장의 길이는 적어도 1이상이며 255이하다.

출력

각각의 테스트 케이스에 대해, 가장 빈번하게 나타나는 문자를 출력하거나 빈번하게 나타나는 문자가 여러 개일 경우 '?'를 출력한다.

접근 방법

주의할 점 : getline(cin, str)으로 공백 포함한 한 줄을 받기 전에, cin>>T 이후의 입력 버퍼를 비우도록 하자!! 입력 버퍼 비우지 않으면 입력한 값을 T에 저장하고 남은 '\n'가 밀려서 그 다음의 getline(cin, str)의 str로 들어가게 돼서 입력값이 하나씩 밀리는 문제가 발생한다. 자세한 내용은 아래의 링크를 참고하자.

https://namwhis.tistory.com/entry/cin%EA%B3%BC-getline%EC%9D%84-%EA%B0%99%EC%9D%B4-%EC%82%AC%EC%9A%A9%ED%95%A0%EB%95%8C-cinignore%EC%9D%B4-%ED%95%84%EC%9A%94%ED%95%9C-%EC%9D%B4%EC%9C%A0-%EA%B8%B0%EB%A1%9D

1) T를 입력받은 후, cin.ingnore()을 이용하여 입력 버퍼를 비워준다. (다음에 공백을 포함한 문자열을 받아야 하기 때문에)

2) 각 테스트케이스는 소문자와 공백이므로, 각 소문자를 배열의 인덱스로 삼아서 ('a'가 아스키코드로 97이므로 97을 뺀 수를 인덱스로 삼는다) 해당 소문자가 몇번 나왔는지 수를 배열에 저장한다.

3) 가장 빈번하게 나타나는 문자가 여러개인지를 판단하기 위해 벡터에 pair를 넣는다. pair의 first는 문자가 출력된 수, pair의 second는 그 문자를 저장한다.

4) 벡터를 내림차순 정렬한다.

5) 가장 빈번하게 나타나는 문자가 여러개이면 vec[0].first 와 vec[1].first가 같을 것이기 때문에 이 경우에는 ?를 출력한다.

6) 이외에는 가장 빈번한 문자인 vec[i].second를 출력한다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;

int alphaCntArr[26] = {0,};
//a = 97
int main(){

   int T; cin >> T; cin.ignore();
   for(int t=1; t<=T; t++){
       memset(alphaCntArr, 0, sizeof(alphaCntArr));
       string str;
       getline(cin, str);

       for(int i = 0; i<str.length(); i++){
           if(str[i] == ' ') continue;

           alphaCntArr[str[i]-97]++;
       }

        vector<pair<int,char>> vec;
       for(int i = 0; i<26; i++){
           vec.push_back(make_pair(alphaCntArr[i], i+97));
       }

        sort(vec.begin(), vec.end(), greater<>());

        if(vec[0].first==vec[1].first){
            cout << "?\n";
        }
        else {
                cout << vec[0].second << "\n";
        }
   }

    return 0;
}

문제 링크 : https://www.acmicpc.net/problem/20437

문제

작년에 이어 새로운 문자열 게임이 있다. 게임의 진행 방식은 아래와 같다.

1. 알파벳 소문자로 이루어진 문자열 W가 주어진다.
2. 양의 정수 K가 주어진다.
3. 어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이를 구한다.
4. 어떤 문자를 정확히 K개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이를 구한다.

위와 같은 방식으로 게임을 T회 진행한다.

입력

문자열 게임의 수 T가 주어진다. (1 ≤ T ≤ 100)

다음 줄부터 2개의 줄 동안 문자열 W와 정수 K가 주어진다. (1 ≤ K ≤ |W| ≤ 10,000) 

출력

T개의 줄 동안 문자열 게임의 3번과 4번에서 구한 연속 문자열의 길이를 공백을 사이에 두고 출력한다.

만약 만족하는 연속 문자열이 없을 시 -1을 출력한다.

접근 방법

먼저 문제를 풀기 전에 조건의 3번, 4번에 적힌 문장 의미를 잘 이해해야 한다.

3. 어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이를 구한다.

  는 결국 조건 4와 같이 연속 문자열의 양 끝이 그 어떤 문자로 이루어졌을 것이다.

 (W = "baa", K = 2  or W = "aaa", K=2  or W = "abaa", K = 2)

4. 어떤 문자를 정확히 K개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이를 구한다.

   이 조건은 어떤 문자와 해당 문자가 같으므로, 역시 연속 문자열의 양 끝이 그 어떤 문자로 이루어졌을 것이다.

  (W = "baaabaab", K = 5)

start 인덱스를 정하고, start 인덱스를 기준으로 end 인덱스를 옮겨가면서 완전탐색을 하면 시간초과가 난다.

그래서 W의 모든 문자에 대해서가 아닌,

K개 이상 나온 알파벳을 후보로 정한 후에, 그 후보들에 대해서만 인덱스 검사를 해서 최소와 최대 길이를 구하면 된다.

먼저 예시인 W = "abaaaba", K=3에 대해 살펴보자.

크기가 26인 벡터 배열을 만든다음, W에서 해당 알파벳의 인덱스를 벡터에 저장한다. 

i=0일때의 W[0] = 'a'이므로 a를 의미하는 W[0]-97 = 0을 인덱스로 지정한다.

i=1일때의 W[1] = 'b'이므로 b를 의미하는 W[1] - 97 = 1을 인덱스로 지정한다.

이제 벡터배열을 돌면서 크기가 K이상인 벡터에 대해서만 검사를 진행한다.

문자열에 K개가 포함되야 하므로, 검사는 (벡터크기 - K + 1) 번 진행한다. 즉 j = 0부터 j = vecList[i].size() - K 까지 검사한다. 

또한 K개를 포함하는 연속문자열의 길이를 구하기 위해서는, 

vecList[i][j+K-1] - vecList[i][j] + 1

와 같이 구할 수 있다.

위의 i = 0일 때, 벡터 {0,2,3,4,6}을 예로 들어보면 

3-0 +1 = 4 (aaba)

4-2 +1 = 3 (aaa)

6-3 + 1 = 4 (aaba)

와 같이 구할 수 있다. 

//
//  문자열_BOJ20437_문자열게임2.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/07/09.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <vector>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;

int main(){
    
    int T;
    cin >> T;
    
    vector<int> vecList[26];

    for(int test_case = 1; test_case <=T; test_case++){
        string W;
        int K;
        cin >> W >> K;
        
        int mini = 100000;
        int maxi = 0;
        for(int i = 0; i<26; i++) vecList[i].clear();
        for(int i = 0; i<W.length(); i++){
            int num = W[i] - 97;    // 's' = 18
            vecList[num].push_back(i);      //해당 문자의 인덱스를 넣음.
        }
       
        for(int i = 0; i<26; i++){
            int vsize = (int)vecList[i].size();
            if(vsize >= K){ //조건을 만족하는 후보 알파벳들만 고려해서 탐색함으로써 시간 초과 해결.
                for(int j = 0; j<=vsize - K; j++){  //최소 K개를 포함해야 하므로, 만약 vsize=5이고, K=3이면 j=0,1,2까지만 검사하면 됨.
                    mini = min(mini, vecList[i][j+K-1] - vecList[i][j] + 1);
                    maxi = max(maxi, vecList[i][j+K-1] - vecList[i][j] + 1);
                }
            }
        }
        
        if(mini == 100000 || maxi == 0) cout << -1 << "\n";
        else cout << mini << " " << maxi << "\n";
        
    }
    
    return 0;
}

문제 링크 : https://www.acmicpc.net/problem/16916

문제

문자열 S의 부분 문자열이란, 문자열의 연속된 일부를 의미한다.

예를 들어, "aek", "joo", "ekj"는 "baekjoon"의 부분 문자열이고, "bak", "p", "oone"는 부분 문자열이 아니다.

문자열 S와 P가 주어졌을 때, P가 S의 부분 문자열인지 아닌지 알아보자.

입력

첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다.

출력

P가 S의 부분 문자열이면 1, 아니면 0을 출력한다.

접근방법

처음에는 문자열의 각 인덱스에 대해서 substr()를 호출해서 검사했는데, 시간초과가 났다.

그래서 KMP알고리즘을 이용하였다.

KMP 알고리즘을 사용하기 위해서는 주어진 문자열에 대해 먼저 Failure Function을 구해야한다.

*Failure Function 이란? 

  - KMP 알고리즘에서 mismatch 발생 시, 다음번에 비교해야 할 Pattern 상의 위치를 알려주는 함수.

  - Failure Function F(j) : index[0] ~ index[j] 까지 proper prefix와 proper suffix가 매치되는 최대 길이를 저장한다.

먼저 왼쪽 그림을 보면 쉽게 이해할 수 있다.

1) j = 5 에서 mismatch가 발생했다.

2) F[j-1] = F[4]를 확인한다. 

3) F[4] = 2 이므로 index = 0과 1에 해당하는 앞의 두 문자("ab"는 검사할 필요 없이 스킵한다.)

4)  index = 2 부터 재탐색한다.

* F[4] = 2 라는 것은 가장 길게 match 되는 p.p와 p.s 길이를 의미하기도 하지만, 다음 스텝에서 비교해야할 pattern의 index를 의미하기도 한다. 

Failure Function을 구하는 코드는 아래와 같다.

void FailFunc(string pattern){
	int len = pattern.length();
    int j = 0;
	vector<int> failVec(len, 0);	//0번 인덱스는 무조건 0
    
    for(int i = 1; i<len; i++){
    	while(j>0 && pattern[i] != pattern[j]){		//j = 0이거나 mismatch 발생하면 -> 비교 시작 지점(j) 위치 조정. 
		j = failVec[j-1];
        }
        
        if(pattern[i] == pattern[j]) failVec[i] = ++j;		//일치하면 계속 i와 j 증가시켜나감.
    }
}

이제 위의 코드에 따라 차근차근 "abaaba"의 Failure Function을 구해보자.

step 1) i = 1, j = 0에서 시작한다.

step 2) i = 1, j = 0 -> mismatch -> i++ (아직 j가 0 이므로 i만 증가)

step 3) i = 2, j = 0 -> match -> i++, ++j  -> F[2] = 1

step 4) i = 3, j = 1 -> mismatch -> j = F[1-1] = F[0] = 0

step 5) i = 3, j = 0 -> match -> F[i] = ++j -> F[3] = 1

step 6) i = 4, j = 1 -> match -> F[i] = ++j -> F[4] = 2

step 7) i = 5, j = 2 -> match -> F[i] = ++j -> F[5] = 3

이제 Failure Function을 이용해서 KMP알고리즘으로 전체 문자열에서 주어진 부분 문자열을 찾을 수 있는지 검사해보자.

수도코드는 위와 같다. Failure Function을 구하는 알고리즘과 유사하다.

match가 되었을 때, pattern을 가리키는 j가 문자열의 끝을 가리키고 있으면 부분 문자열을 찾은것이다! 

코드로 구현하면 아래와 같다.

bool KMP(string S, string P){
	vector<int> failVec = FailFunc(string P);
    int j = 0;
    for(int i = 0; i<S.length(); i++){
    	while(j>0 && S[i] != P[j]){					//mismatch면 Failure Function 참고
    		j = failVec[j-1];
    	}
        
    	if(S[i] == P[j]){
        	if(j == P.length() -1) return true;		//match인데 끝까지 검사한거면 
            else j+=1;								//아직 끝까지 검사 안 했으면 j 증가
        }
    }
   return false;
}

구현 코드

//
//  문자열_BOJ16916_부분문자열.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/07/09.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

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

vector<int> failFunc(string P){
    int plen = (int)P.length();
    vector<int> failVec(plen, 0);
    int j = 0;
    for(int i = 1; i<plen; i++){
        while(j>0 && P[i]!=P[j]){
            j = failVec[j-1];
        }
        if(P[i] == P[j]){
            failVec[i] = ++j;
        }
    }
    return failVec;
}

int KMP(string S, string P){
    vector<int> failVec = failFunc(P);
    int j = 0;
    
    for(int i = 0; i<S.length(); i++){      //S 길이 기준
        while(j>0 && S[i] != P[j]){
            j = failVec[j-1];
        }
        if(S[i] == P[j]){
            if(j== P.length()-1) return 1;      //P 길이 기준
            else j+=1;
        }
    }
    return 0;
    
}

int main(){
    
    string S, P;
    cin >> S >> P;
 
    N = (int)S.length();
    
    cout << KMP(S, P);

    return 0;
}

문제 링크 : https://www.acmicpc.net/problem/1543

문제

세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한다. 예를 들어, 문서가 abababa이고, 그리고 찾으려는 단어가 ababa라면, 세준이의 이 함수는 이 단어를 0번부터 찾을 수 있고, 2번부터도 찾을 수 있다. 그러나 동시에 셀 수는 없다.

세준이는 문서와 검색하려는 단어가 주어졌을 때, 그 단어가 최대 몇 번 중복되지 않게 등장하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 문서가 주어진다. 문서의 길이는 최대 2500이다. 둘째 줄에 검색하고 싶은 단어가 주어진다. 이 길이는 최대 50이다. 문서와 단어는 알파벳 소문자와 공백으로 이루어져 있다.

출력

첫째 줄에 중복되지 않게 최대 몇 번 등장하는지 출력한다.

접근 방법

substr()함수를 이용해서 풀 수 있는 간단한 문자열 비교 문제였다. 그런데 생각보다 정답률이 낮아서 의아했는데 문제를 풀어보니 주의할 점을 고려해주지 않으면 오답처리되기 쉽다는 것을 알 수 있었다. 문제 조건을 꼼꼼히 확인하는것이 중요하다는 것을 새삼 깨달을 수 있게 해주는 문제였다. 주의할 점은 다음과 같이 두 개 정도 있다.

주의할 점 1)

문서의 길이가 단어 길이보다 작은 경우에는 예외 처리를 따로 해줘야 한다. 이 부분을 고려해주지 않아서 런타임 에러가 났다.

주의할 점 2)

일치하는 문자열을 찾은 뒤, 중복되지 않도록 단어의 길이만큼 문서를 스킵하기 위해 인덱스를 임의로 조정해주는데, 

이때 i+=wordLen이 아닌 i+=(wordLen -1)만큼만 증가시켜줘야한다.

왜냐하면 어짜피 for문 안에서 i++라는 증감식에 의해 인덱스가 1 증가하기 때문이다.

//
//  문자열_BOJ1543_문서검색.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/07/07.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

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

int main(){

    string documents, word;
    getline(cin,documents);
    getline(cin, word);
    
    int ans = 0;
    
    int wordLen = (int)word.length();
    
    if(documents.length() < wordLen) cout << 0;	//1. 예외처리 해주지 않으면 런타임에러
    else{
        for(int i = 0; i<=documents.length()-wordLen; i++){
            
            if(documents[i] == word[0]){
                string sub = documents.substr(i, wordLen);
                if(sub==word){
                    ans++;
                    i += (wordLen -1);		//2. for문에서 어짜피 i증가되니까 여기서는 1 감소
                }
            }
        }
        
        cout << ans;
    }

    return 0;
}

문제 링크 : https://www.acmicpc.net/problem/5052

문제

전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.

전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.

예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자

• 긴급전화: 911
• 상근: 97 625 999
• 선영: 91 12 54 26

이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다.

입력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 하나씩 주어진다. 전화번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다.

출력

각 테스트 케이스에 대해서, 일관성 있는 목록인 경우에는 YES, 아닌 경우에는 NO를 출력한다.

접근 방법

처음에는 3중 포문을 돌면서 현재 문자열에 대해 n-1개의 전화번호를 다 돌면서 비교하는 완전탐색을 했는데 시간초과가 났다.

그러나 아래의 경우를 생각해보면 문자열을 sort() 한 뒤, 현재 문자열을 기준으로 삼고 현재 문자열이 바로 다음 문자열의 접두어가 되는지만 판단하면 시간 안에 해결할 수 있다. 

123

1234

134

=> NO

123

1245

13

=> YES

이때, 현재 문자열의 길이가 다음 문자열의 길이보다 길면 접두어가 될 수 없으므로 스킵하면 더욱 시간을 단축할 수 있다.

//
//  문자열_BOJ5052_전화번호목록.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/07/07.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

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

int main(){
    int t; cin >> t;
    for(int test_case = 1; test_case<=t; test_case++){
        int n; cin >> n;
        string str;
        vector<string> vecStr;
        for(int i = 0; i<n; i++){
            cin >> str;
            vecStr.push_back(str);
        }
        sort(vecStr.begin(), vecStr.end());
        bool flag = true;
        for(int i = 0; i<vecStr.size()-1; i++){
            
            string cur = vecStr[i];
            string next = vecStr[i+1];
            flag = true;
            if(cur.length() > next.length()) continue;
            if(cur == next.substr(0, cur.length())){
                flag = false;
                break;
            }
        }
        if(!flag) cout << "NO\n";
        else cout << "YES\n";
    }

    return 0;
}