백준 6550번 - 부분 문자열 (C++)

유형: 그리디

문제: https://www.acmicpc.net/problem/6550

6550번: 부분 문자열

 

입출력 방식

입력받는 개수가 몇개인지 모르는 경우이다. 이런 경우를 입력받는 방법은 여러 가지가 있는 것 같다.

이 글에 정리가 잘 되어있다! https://scarlettb.tistory.com/69

가장 직관적인 방법은 while문 조건에 cin 또는 scanf를 넣는 것이다.

다만 scanf를 넣을 땐 scanf(...) != EOF 형식으로 써야하는 것 같다.

do while 문을 사용하는 방법도 있으나, 내 IDE에서는 제대로 실행이 안돼서 이건 쓰지 않기로 했다.

사실 while문 조건에 cin을 넣는 것도 IDE에선 끝이 안나는데, 백준에선 제대로 실행이 됐다.

가장 중요한 풀이는 comp 함수에 따로 작성했다.

#include "iostream"

using namespace std;

void comp(string s, string t){
	// ...
}

int main(){
    ios::sync_with_stdio(0);

    string s, t;

    while (cin >> s >> t){
        comp(s, t);
    }

    return 0;
}

 

풀이 1

t의 문자열에서 특정 문자를 계속 뺐을 때 s 문자열과 동일한 것이 있으면 정답이다.

t의 원소를 하나씩 돌면서, s와 일치하는 문자가 있다면 cnt 값을 하나 증가시킨다.

이렇게 하면 t 문자열에서 s 문자열과 동일한 순서가 포함되어있는지 알 수 있다.

주의할 점은, cnt++ 연산을 할 때 s의 범위를 초과하는 경우는 예외처리가 필요하다.

void comp(string s, string t){
    int cnt = 0;

    for(auto ch : t){
        if(ch == s[cnt]) cnt ++;
        if(cnt == s.size()) {
            cout << "Yes" << "\n";
            break;
        }
    }

    if(cnt != s.size()) cout << "No" << "\n";
}

 

풀이 2

원리는 풀이 1과 동일하다. 예외처리 조건문을 넣은 위치만 다르다.

더 짧아서 보기에는 깔끔한데, 이런 예외처리가 바로바로 생각이 안나는게 문제였다. (처음엔 if문 조건이 그냥 ch == s[cnt] 뿐이었다.)

void comp(string s, string t){
    int cnt = 0;

    for(auto ch : t){
        if(cnt < s.size() && ch == s[cnt]) cnt ++;
    }

    if(cnt == s.size()) cout << "Yes";
    else cout << "No";
    cout << "\n";
}