[알고리즘] 9996번: 한국이 그리울 땐 서버에 접속하지

0. 문제

 

9996번: 한국이 그리울 땐 서버에 접속하지

 

문제

선영이는 이번 학기에 오스트레일리아로 교환 학생을 가게 되었다.

호주에 도착하고 처음 며칠은 한국 생각을 잊으면서 즐겁게 지냈다. 몇 주가 지나니 한국이 그리워지기 시작했다.

선영이는 한국에 두고 온 서버에 접속해서 디렉터리 안에 들어있는 파일 이름을 보면서 그리움을 잊기로 했다. 매일 밤, 파일 이름을 보면서 파일 하나하나에 얽힌 사연을 기억하면서 한국을 생각하고 있었다.

어느 날이었다. 한국에 있는 서버가 망가졌고, 그 결과 특정 패턴과 일치하는 파일 이름을 적절히 출력하지 못하는 버그가 생겼다.

패턴은 알파벳 소문자 여러 개와 별표(*) 하나로 이루어진 문자열이다.

파일 이름이 패턴에 일치하려면, 패턴에 있는 별표를 알파벳 소문자로 이루어진 임의의 문자열로 변환해 파일 이름과 같게 만들 수 있어야 한다. 별표는 빈 문자열로 바꿀 수도 있다. 예를 들어, "abcd", "ad", "anestonestod"는 모두 패턴 "a*d"와 일치한다. 하지만, "bcd"는 일치하지 않는다.

패턴과 파일 이름이 모두 주어졌을 때, 각각의 파일 이름이 패턴과 일치하는지 아닌지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 파일의 개수 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄에는 패턴이 주어진다. 패턴은 알파벳 소문자와 별표(아스키값 42) 한 개로 이루어져 있다. 문자열의 길이는 100을 넘지 않으며, 별표는 문자열의 시작과 끝에 있지 않다.

다음 N개 줄에는 파일 이름이 주어진다. 파일 이름은 알파벳 소문자로만 이루어져 있고, 길이는 100을 넘지 않는다.

출력

총 N개의 줄에 걸쳐서, 입력으로 주어진 i번째 파일 이름이 패턴과 일치하면 "DA", 일치하지 않으면 "NE"를 출력한다.

참고로, "DA"는 크로아티어어로 "YES"를, "NE"는 "NO"를 의미한다.

예제 입력 1

3
a*d
abcd
anestonestod
facebook

예제 출력 1

DA
DA
NE

예제 입력 2

6
h*n
huhovdjestvarnomozedocisvastan
honijezakon
atila
je
bio
hun

예제 출력 2

DA
DA
NE
NE
NE
DA

 

---

1. 문제 이해

1. N, 패턴, N개의 파일 이름을 입력받는다.
2. 패턴을 *을 기준으로 split 한다.
3. 파일의 앞과 뒤가 패턴에 속하는지 확인한다.
4. NA, DE를 출력한다.

 

---

2. 제출

 

가. 런타임 에러

// 백준 9996번: 한국이 그리울 땐 서버에 접속하지
#include <iostream>
#include <vector>

using namespace std;

vector<string> ret;
int n;
string pattern, s;

void split(string input, string delimiter){
	auto pos = 0;
	while((pos = input.find(delimiter))!=string::npos){
		string token = input.substr(0, pos);
		ret.push_back(token);
		input.erase(0, pos + delimiter.length());
	}
	ret.push_back(input);
	return;
}

int main(){
	cin >> n >> pattern;
	split(pattern, "*");
	for(int i=0; i<n; i++){
		cin >> s;
		if(ret[0] == s.substr(0,ret[0].length()) && ret[1] == s.substr(s.length()-ret[1].length(),ret[1].length())){
			cout << "DA" << "\\n";
		}else{
			cout << "NE" << "\\n";
		}
	}
	ret.clear();
	return 0;
}

런타임 에러가 발생한다.

 

런타임 에러가 발생하는 이유는 여러 가지가 있을 수 있지만, 이 코드의 경우 아마도 문자열 인덱싱이 문제일 수 있다.

 

코드에서는 입력 문자열 s의 앞부분과 뒷부분을 substr 함수를 이용해 추출하고 있다.

 

이때, s.length()-ret[1].length()가 음수가 되는 경우에는 substr 함수가 예외를 발생시킬 수 있다.

예를 들어, 패턴이 "abc*defg"이고, 입력 문자열이 "ab"인 경우에는 s.length()-ret[1].length()가 음수가 된다.

이런 경우에 substr 함수는 예외를 발생시킨다.

 

---

나. 수정

// 백준 9996번: 한국이 그리울 땐 서버에 접속하지
#include <iostream>
#include <vector>

using namespace std;

vector<string> ret;
int n;
string pattern, s;

void split(string input, string delimiter){
	auto pos = 0;
	while((pos = input.find(delimiter))!=string::npos){
		string token = input.substr(0, pos);
		ret.push_back(token);
		input.erase(0, pos + delimiter.length());
	}
	ret.push_back(input);
	return;
}

int main(){
	cin >> n >> pattern;
	split(pattern, "*");
	for(int i=0; i<n; i++){
		cin >> s;
		if(s.length() < ret[0].length() + ret[1].length()){
			cout << "NE" << "\\n";
		}else{
			if(ret[0] == s.substr(0,ret[0].length()) && ret[1] == s.substr(s.length()-ret[1].length(),ret[1].length())){
				cout << "DA" << "\\n";
			}else{
				cout << "NE" << "\\n";
			}
		}
	}
	ret.clear();
	return 0;
}

모든 것에 앞서 최소한 주어진 패턴보다는 파일의 이름이 길어야 한다.

 

pattern보다 주어지는 파일 이름이 짧을 경우 NE를 출력하도록 조건문을 추가한다.

 

if(s.length() < ret[0].length() + ret[1].length()){
	cout << "NE" << "\\n";
}else{ ... }

 

---

다. 다른 사람의 코드

#include<bits/stdc++.h> 
using namespace std;   
int n; 
string s, ori_s, pre, suf; 
int main(){
    cin >> n;
    cin >> ori_s;  
    int pos = ori_s.find('*');  
    pre = ori_s.substr(0, pos); 
    suf = ori_s.substr(pos + 1); 
    for(int i = 0; i < n; i++){
        cin >> s; 
        if(pre.size() + suf.size() > s.size()){
            cout << "NE\\n";
        }else{
            if(pre == s.substr(0, pre.size()) && suf == s.substr(s.size() - suf.size())) cout << "DA\\n";
            else cout <<"NE\\n";  
        } 
    } 
    return 0;
}

해당 코드에 비하여 나의 코드는 지나치게 일반화했다.

 

특히 pre, suf을 구하는 방식이 나의 비해서 더 간단하다.

 

또한 substr(pos)처럼 입력하면 pos부터 끝까지 문자열을 반환한다.

 

---