알고리즘 :: 백준 :: 9996 - 한국이 그리울 땐 서버에 접속하지

 

 

 

 

 

 

❔문제

🔗문제링크

 

🔄 문제 및 입출력 조건 파악

입력

• 파일 개수 N ≤ 100
• 각 파일명 길이 ≤ 100인 소문자
• 패턴은 별표(*) 1개가 있는 길이 ≤ 100인 소문자

출력

• 패턴 일치 "DA"
• 패턴 불일치 "NE"

✏️ 문제풀이

주어진 패턴은 별표(`*`)를 기준으로 (접두사) / (`*`) / (접미사) 세 가지 부분으로 나눌 수 있습니다.

 

입력된 파일명의

• 앞부분('접두사'의 길이만큼)이 '접두사'와 일치해야 하고
• 뒷부분('접미사'의 길이만큼)이 '접미사'와 일치하면 그 파일명은 패턴과 일치한다고 판단합니다.

패턴 내에서 `*`의 위치(i.e. `pos`)를 찾으면

• 접두사는 `[0~pos)`까지의 위치,
• 접미사는 `[pos + 1, 패턴길이)`까지의 위치입니다.

auto pos = pattern.find('*');
patL = pattern.substr(0, pos);
patR = pattern.substr(pos + 1);

 

[주의할 점]

놓치기 쉬운 판단조건이 하나 있습니다.

바로 파일명의 길이가 접두사의 길이 + 접미사의 길이보다는 크거나 같아야 한다는 점입니다.

 

예를들어, 패턴이 `ab*ab`라면, (접두사: `ab`, 접미사: `ab`)

입력받은 파일명이 `ab`라면, 당연히 패턴과 일치하지 않는것을 알 수 있습니다.
그러나, 위 판단조건으로는 접두사 == 파일명이고 접미사 == 파일명이므로 패턴과 일치한다고 잘못 판단합니다.
그러므로 주어진 파일명의 길이가 접두사 길이 + 접미사 길이여야 합니다.

📝 코드

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

int N;
string pat, patL, patR, name;

bool check (const string& name) {
	int lenL = patL.length(), lenR = patR.length(), lenName = name.length();
	// chek name if shorter than pattern
	if (lenName< (lenL + lenR)) return false;
	// check each part of pattern with name
	if (patL != name.substr(0, lenL) ||  
		patR != name.substr(lenName - lenR)) return false;
	return true;
}


int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	
	cin >> N;
	cin >> pat;
	
	auto aster = pat.find('*');
	patL = pat.substr(0, aster);
	patR = pat.substr(aster + 1);
	
	while (N--) {
		cin >> name;
		cout << (check(name) ? "DA" : "NE") << '\n';
	}
}

 

🔗 코드 링크

🕧 결과