<백준> 15786번 Send me the money (IUPC)

2018 인하대학교 프로그래밍 경진대회(IUPC) G번 문제

문제

석규는 해외로 저렴하고 간편하게 송금할 수 있는 센트비 서비스를 이용하여 CTP 왕국에 놀러간 형동이에게 돈을 보내주려고 한다. 하지만 안타깝게도 석규는 센트비 비밀번호를 까먹어버렸고 돈을 보내주지 못한다. 

다행히도 석규는 평소에 포스트잇에 비밀번호를 적어놓는다. 비밀번호는 알파벳 대문자로만 구성이 되어있으며 석규는 이 중 일부를 정확히 기억하고 있다.

석규는 포스트잇을 확인하여 비밀번호를 입력하려고 했지만, 포스트잇은 여러 장 존재했고 이 중 어떤 포스트잇이 센트비 비밀번호가 적힌 포스트잇인지 모른다.

석규는 센트비 비밀번호의 알파벳 중 등장하는 순서대로 N글자만 정확히 기억하고 있으며 포스트잇 중에 이 순서를 갖는 포스트잇이 센트비 비밀번호일 가능성이 있는 포스트잇이다. 

예를 들어, 석규가 ABB를 기억한다면 BBAB이 적힌 포스트잇은 비밀번호일 가능성이 없고, HAEBBC가 적힌 포스트잇은 비밀번호일 가능성이 있다. 

석규는 형동이에게 송금해주기 위해 포스트잇들 중 비밀번호가 적힌 포스트잇일 가능성이 있는 포스트잇들을 따로 분류하려고 한다. 석규가 기억하는 알파벳 N글자와 포스트잇 M개가 주어질 때, 해당 포스트잇에 적힌 알파벳이 비밀번호일 가능성이 있는지 여부를 판단하여 보자.

입력

입력의 첫째 줄에 석규가 기억하는 원본 알파벳의 수 N(1 ≤ N ≤ 100)과 포스트잇의 개수 M(1 ≤ M ≤ 1000)이 주어진다. 다음 줄에 길이가 N인 알파벳 대문자로 이루어진 문자열 S가 주어진다. 이 후 M개의 줄에 알파벳 대문자로 이루어진 판별해야 할 포스트잇들이 주어진다. 모든 포스트잇에 적힌 문자열은 1000자 이하이다.

출력

M개의 줄에 가능성 여부를 “true” , “false”로 답하여라.

문제 풀이

간단한 문제이지만 true를 True라고 써서 두번 틀렸다... 확실히 웹 컴파일러로 프로그래밍 하니 잔 실수가 많은거 같다

알파벳 N글자(=S)의 순서대로 있어야 비밀번호일 가능성이 있으므로  문자열로 받은다음 포스트잇에 적힌 문자열을 각각 비교한다. 예를 들어 PAPP라는 문자열 S가 주어지고 PPAPP라는 문자열 E가 주어진다면

1. S[0] 과 E[0]을 비교한다. 이때 똑같은 문자 P이므로 S의 인덱스를 1 올린다. 

2. S[1] 과 E[1]을 비교한다. 이때 문자가 각각 A와 P 이므로 S의 인덱스는 그대로 둔다.

3. S[1] 와 E[2]을 비교한다. 이때 똑같은 문자 A 이므로 S의 인덱스를 1 올린다.

4. 이와 같은 과정을 반복하며 S의 문자열 끝에 도착하면 문자열 E는 비밀번호일 가능성이 있다.

이것을 C++코드로 나타내면 다음과 같다:

#include <iostream>
#include <cstring>
using namespace std;
 
bool check(char* temp, char* a, int N){
    int cnt=0;
    for(int i=0;i<strlen(temp);i++){
        if(temp[i]==a[cnt]){
            cnt++;
        }
        if(cnt==N){
            return true;
        }
    }
    
    return false;
}
 
int main() {
    int N, M;
    scanf("%d %d",&N,&M);
    char* temp = new char[1000];
    char* a = new char[N];
    cin>>a; 
    for(int i=0;i<M;i++){
        cin>> temp;
        if(check(temp,a,N)){
            cout<<"true"<<endl;
        }else{
            cout<<"false"<<endl;
        }
    }
    
}