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

9996번: 한국이 그리울 땐 서버에 접속하지 (acmicpc.net)

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

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

다국어

시간 제한          메모리 제한                    제출                          정답                   맞힌 사람              정답 비율

1 초

128 MB

11553

3232

2473

27.260%

문제

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

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

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

 

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

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

파일 이름이 패턴에 일치하려면, 패턴에 있는 별표를 알파벳 소문자로 이루어진 임의의 문자열로 변환해 파일 이름과 같게 만들 수 있어야 한다. 별표는 빈 문자열로 바꿀 수도 있다. 예를 들어, "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

 

흐름

글씨가 ...

abc*de가 패턴일때 패턴 앞부분인 abc와 패턴 뒷부분인 de가 문자열과 일치하는지 조사한다.

패턴 앞부분은 차례대로, 패턴 뒷부분은 뒤에서부터 조사한다.

틀린 코드

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

int n, sIndex;
string pat, str; 
vector<string> inp; //파일이름 저장하는 벡터 
bool flag; //일치 여부 flag, 초기값 false 

int main(){
	//1. 문제 입력받기 
	cin >> n >> pat;
	for(int i=0;i<n;i++){
		cin >> str;
		inp.push_back(str);
	}
	//2. *의 인덱스를 파악하기
	for(int i=0;i<pat.length();i++){
		if(pat[i]=='*') sIndex=i;
	} 
	//3. 한 문자열씩 패턴과 일치하는지 파악하기
	for(string s:inp){
		flag=0; //일치하지않으면 true 
		//3-1. 0~index-1 (패턴의 앞부분) 일치 조사  
		for(int i=0;i<sIndex;i++){
			if(s[i]==pat[i]) continue;
			else { //일치하지않으면 
				cout << "NE" << "\n";
				flag=1;  
				break;
			}
		}
		if(flag==1) continue; //일치하지않으면 더이상 검사하지않음 
		
		//3-2. index+1~ 패턴길이-1 (패턴의 뒷부분) 일치 조사
		int pl = pat.length();//패턴의 길이
		int sl = s.length(); //문자열 길이 
		for(int i=0;i<pl-1-sIndex;i++){ // 패턴의 뒷부분 글자개수만큼 반복 
			if(s[sl-1-i] == pat[pl-1-i]) continue; //끝 인덱스에서 i만큼 빼준값 비교 
			else{
				cout << "NE" << "\n";
				flag=1;
				break;
			}
		}
		//패턴과 문자열이 일치하면 DA 출력 
		if(flag==0) cout << "DA" << "\n"; 
	} 
	return 0;
}

반례가 더 있을까?

유의할 점

• <bits/stdc++.h>에서 변수명을 index로 했을때 백준 채점 결과 컴파일에러가 떴다. 변수명은 count는 cnt, size는 sz, index는 ix처럼 줄여써야겠다(나만의 변수명 만들기)

반례 존재

패턴이 ab*ab
글자가 ab

내 코드: 일치 => 하지만 틀렸다. 패턴과 일치하지않는다.

글자 길이는 패턴 길이보다는 길어야한다.

abab일때 패턴은 일치할 것이다. 

 

선생님 코드

#include <bits/stdc++.h>
using namespace std;
int n;
string s, ori_s, pre,suf;
int main(){
	//1. 입력받기 
	cin >> n;
	cin >> ori_s;
	//2. 패턴을 *을 기준으로 pre, suf로 나누기 
	int pos = ori_s.find('*'); // * 인덱스 반환 
	pre=ori_s.substr(0,pos);
	suf = ori_s.substr(pos+1);
	//3. 패턴에 부합하는지 비교 
	for(int i=0;i<n;i++){
		cin >> s;
		// ✅ 반례 확인: 문자열은 패턴보다는 길어야한다. 
		if(pre.size()+suf.size()>s.size()) cout << "NE\n";
		//pre,suf 비교 
		else{
			if (pre == s.substr(0, pre.size()) && (suf == s.substr(s.size()-suf.size()))){
				cout << "DA\n";
			} 
			else cout << "NE\n";
		}
	}
	return 0;	
}

포인트

• 어떤 문자의 인덱스를 찾을때는 string 멤버함수인 find를 사용하자.
• 문자를 비교할때는 문자 하나하나 비교하는 것보다는 쪼개서 비교하자.
• 문자열을 크게 쪼갤때는 substr 함수를 사용하자. (구분자가 반복되면 split 함수(따로 구현해야함) 사용)
• 어떤 문자의 인덱스(위치)가 2이면 그 문자 앞에 두 글자가 있다.
• 뒤에서 2글자를 추출하고 싶으면 문자열길이-2(추출할 글자수)가 추출 시작할 문자의 인덱스가 된다.
• 굳이 문자열을 저장할 필요없으면 저장하지말고, 입력받은 값을 바로 이용하자.

substr(시작 인덱스, 추출 글자수)
또는
substr(시작 인덱스) : 시작 인덱스부터 끝까지 문자열 추출

 

최종코드(변수명 제외하고 선생님 코드와 같다.)

#include <bits/stdc++.h>
using namespace std;
int n, pos;
string pat, s, pre, suf;
int main(){
	//1. 문제 입력받기 
	cin >> n >> pat;
	//2. 패턴 pre,suf로 나누기 
	pos = pat.find('*');
	pre=pat.substr(0,pos); //0번째부터 ast 인덱스 크기만큼 추출 
	suf=pat.substr(pos+1); //* 뒤부터 추출 
	//3. 패턴 일치여부 확인 
	for(int i=0;i<n;i++){
		cin >> s;
		//문자열의 길이가 패턴 길이보다는 커야한다. 
		if(pre.size()+suf.size()>s.size()) cout << "NE\n";
		else{
			//문자열과 pre,suf 비교 
			if(pre==s.substr(0,pre.size()) && suf==s.substr(s.size()-suf.size())) cout << "DA\n";
			else cout << "NE\n";
		}
	}
	return 0;
	
}