Pr.9996 한국이 그리울땐 서버에 접속하지

Pr.9996 한국이 그리울땐 서버에 접속하지

문제

선영이는 이번 학기에 오스트레일리아로 교환 학생을 가게 되었다. </br> 호주에 도착하고 처음 며칠은 한국 생각을 잊으면서 즐겁게 지냈다. 몇 주가 지나니 한국이 그리워지기 시작했다. </br> 선영이는 한국에 두고온 서버에 접속해서 디렉토리 안에 들어있는 파일 이름을 보면서 그리움을 잊기로 했다. 매일 밤, 파일 이름을 보면서 파일 하나하나에 얽힌 사연을 기억하면서 한국을 생각하고 있었다.</br> 어느 날이었다. 한국에 있는 서버가 망가졌고, 그 결과 특정 패턴과 일치하는 파일 이름을 적절히 출력하지 못하는 버그가 생겼다.</br> 패턴은 알파벳 소문자 여러 개와 별표(*) 하나로 이루어진 문자열이다.</br> 파일 이름이 패턴에 일치하려면, 패턴에 있는 별표를 알파벳 소문자로 이루어진 임의의 문자열로 변환해 파일 이름과 같게 만들 수 있어야 한다. 별표는 빈 문자열로 바꿀 수도 있다. 예를 들어, “abcd”, “ad”, “anestonestod”는 모두 패턴 “a*d”와 일치한다. 하지만, “bcd”는 일치하지 않는다.</br> 패턴과 파일 이름이 모두 주어졌을 때, 각각의 파일 이름이 패턴과 일치하는지 아닌지를 구하는 프로그램을 작성하시오.</br>

입력

첫째 줄에 파일의 개수 N이 주어진다. (1 ≤ N ≤ 100) </br> 둘째 줄에는 패턴이 주어진다. 패턴은 알파벳 소문자와 별표(아스키값 42) 한 개로 이루어져 있다. 문자열의 길이는 100을 넘지 않으며, 별표는 문자열의 시작과 끝에 있지 않다.</br> 다음 N개 줄에는 파일 이름이 주어진다. 파일 이름은 알파벳 소문자로만 이루어져 있고, 길이는 100을 넘지 않는다.</br>

출력

총 N개의 줄에 걸쳐서, 입력으로 주어진 i번째 파일 이름이 패턴과 일치하면 “DA”, 일치하지 않으면 “NE”를 출력한다.</br> 참고로, “DA”는 크로아티어어로 “YES”를, “NE”는 “NO”를 의미한다.</br>

예제 입력

3
a*d
abcd
anestonestod
facebook

예제 출력

DA
DA
NE

풀이과정

전제조건

1. 시간 복잡도, 공간 복잡도
   • 공간 복잡도 : 백터의 크기 3으로 고정
   • 시간 복잡도 : 파일의 최대가 100개 이므로 최대O(100)의 시간 복잡도
2. 최대, 최소 조건
   • 문자열의 크기 0~100
3. 사용 알고리즘

   string 주요 메서드

   • substr(int start_pos, int len_size) : start_pos부터 len_size 만큼 문자열 추출
   • find(string delimeter, int start_pos) : start_pos이후 첫번째 delimeter의 위치 반환
   • resvers(int start_pos, int end_pos) : start_pos이상 end_pos미만 문자열 역순변환

   split() 함수 만들기

   vector<string> split(string& input, string delimeter){
     //반환값 정의
     vector<string> result;       
     // 시작점과 첫번째 분리지점 찾기
     int start = 0;
     int end = input.find(delimeter);
     // 마지막 delimeter까지 탐색
     while(end != string::npos){
         result.push_back(input.substr(start,end-start));
         //새로운 시작점 = end + delimeter의 길이
         start = end + delimeter.size();
         end = input.find(delimeter, start);
     }
     //마지막 문자열 넣기
     result.push_back(input.substr(start));
     return result
   }
   

4. 반례

   case1 : prefix와 surfix의 크기가 1이상 </br> ex) sadjkjf*djfkalkdafjl

   case2 : 주어진 문자열이 prefix+surfix보다 작은경우</br> ex ) str = ab*cd, s = ab

제출 코드

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

string str;
vector<string> s;
int n;
vector<string> split(string &s, string delimeter)
{
    vector<string> result;
    int start = 0;
    int end = s.find(delimeter);
    while (end != -1)
    {
        result.push_back(s.substr(start, end - start));
        start = end + delimeter.size();
        end = s.find(delimeter, start);
    }
    result.push_back(s.substr(start));
    return result;
}
int main()
{
    cin >> n;
    cin >> str;
    s = split(str, "*");
    for (int i = 0; i < n; i++)
    {
        string temp;
        cin >> temp;
        if (temp.size() >= s[0].size() + s[1].size() &&
            temp.substr(0, s[0].size()) == s[0] &&
            temp.substr(temp.size() - s[1].size()) == s[1])
        {
            cout << "DA" << "\n";
        }
        else
        {
            cout << "NE" << "\n";
        }
    }
    return 0;
}

해설

생각해볼 점

- split 이외 방법 가능성
- 문제에서 주어진 `*`는 한자리 이므로 크기가 고정 되있음.
- `*`을 중심으로 prefix(접두사)와 surfix(접미사)로 구분 하면 split은 안써도 됨.
- split의 축소 버전

수정방안

- `int pos;`를 활용해 접두사와 접미사를 나눈다.

정답 코드

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

string pre,suf,str;
int n;

int main(){
    cin >> n;
    cin >> str;
    int pos = str.find("*");
    pre = str.substr(0, pos);
    suf = str.substr(pos+1);
    for(int i = 0; i < n; i++){
        string temp;
        cin >> temp;
        if (temp.size() < pre.size()+suf.size()){
            cout << "NE\n";
        } else{
            if(temp.substr(0,pre.size()) == pre && temp.substr(temp.size()-suf.size()) == suf) cout << "DA\n";
            else cout <<"NE\n";
        }
    }
    return 0;
}