[BaekJoon 6550번] 부분 문자열(C++)

※주의※
저의 풀이가 정답은 아닙니다.
다른 코드가 더 효율적이거나 좋을 수 있습니다.
언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 
 

[문제 풀이 사이트]

 
 

6550번: 부분 문자열

 
 

[문제 설명]

 
 

2개의 문자열 s와 t가 주어졌을 때 s가 t의 부분 문자열인지 판단하는 프로그램을 작성하라. 부분 문자열을 가지고 있는지 판단하는 방법은 t에서 몇 개의 문자를 제거하고 이를 순서를 바꾸지 않고 합쳤을 경우 s가 되는 경우를 이야기 한다.
 

 

[입력]

 
 

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 문자열 s 와 t가 빈칸을 사이에 두고 들어온다. s와 t의 길이는 10만을 넘지 않는다.

 
 

[출력]

 
 

입력된 s와 t의 순서대로 s가 t의 부분 문자열인 경우 Yes라 출력하고 아닐 경우 No라고 출력한다.

 
 

[입출력 예]

 
 

입력	출력
sequence subsequence person compression VERDI vivaVittorioEmanueleReDiItalia caseDoesMatter CaseDoesMatter	Yes No Yes No

 
 

[문제 풀이]

 
 

입력이 여러 테스트 케이스로 이루어져 있다.
계속 입력을 받다가 cin.eof() 가 true가 될 때 break 하여 입력을 멈추면 된다.
 
s가 t의 부분 문자열인지 확인하기 위해서는 먼저 s의 길이가 t의 길이보다 긴지 확인해야한다.
만약 s가 t보다 길이가 길다면 부분 문자열이 될 수 없기 때문이다.
고로 이 때는 "No"를 출력하면 된다.
 
만약 s가 t보다 길이가 작다면 문자열 t에서 s의 0번째와 같은 문자를 find 함수를 이용하여 찾는다.
문자열 s의 인덱스를 관리하는 변수를 만들고 찾은 위치 ~ t의 길이 전까지 반복문을 통해 s의 문자와 t의 각 문자와 같은지 확인한다.
같다면 임시 문자열 변수에 해당 문자를 추가해주고 s의 인덱스 변수를 1 증가시켜준다.
 
반복문이 끝나면 임시 문자열 변수가 s와 같은지 확인한다.
같다면 부분 문자열이 될 수 있기 때문에 "Yes"를 출력하고
같지않다면 부분 문자열이 될 수 없기 때문에 "No"를 출력하면 된다.
 
 

[최종 코드]

 
 

[GitHub]

 
 

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

 
 

#include <bits/stdc++.h>
using namespace std;

int main(void) {
    ios_base::sync_with_stdio(false);
    string s; string t;
    while(true) {
        cin >> s >> t;
        if(cin.eof()) break;
        // s가 t의 부분 문자열인가? 확인
        int slen = s.length();
        int tlen = t.length();
        if(slen > tlen) {
            //부분 문자열이 될 수 없음
            cout << "No" << '\n';
        } else {
            int l = t.find(s[0]);
            int sidx = 0;
            string temp;
            for(int i = l; i < tlen; ++i) {
                if(t[i] == s[sidx]) {
                    sidx++;
                    temp += t[i];
                }
            }
            if(temp.compare(s) == 0) {
                cout << "Yes" << '\n';
            } else {
                cout << "No" << '\n';
            }
        }
    }
    return 0;
}