백준 9996번 [한국이 그리울 땐 서버에 접속하지](C++) -yes6686- 티스토리

백준 문제 풀이: 9996 [한국이 그리울 땐 서버에 접속하지]

---

문제 링크: https://www.acmicpc.net/problem/9996

문제 설명:

패턴 문자열에 와일드카드 '*'가 포함된 문자열과 파일명을 비교하여 파일명이 패턴과 일치하는지 확인하는 문제입니다. '*'는 0개 이상의 임의의 문자로 대체될 수 있습니다. 주어진 n개의 파일명 각각에 대해 패턴과의 일치 여부를 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n; // 파일명 개수 입력

    string pstr;
    cin >> pstr; // 패턴 입력

    // 패턴을 * 기준으로 분리
    size_t starPos = pstr.find('*');
    string prefix = pstr.substr(0, starPos); // * 이전 부분
    string suffix = pstr.substr(starPos + 1); // * 이후 부분

    for (int i = 0; i < n; i++) {
        string filename;
        cin >> filename; // 파일명 입력

        if (filename.size() < prefix.size() + suffix.size()) {
            // 파일명이 패턴보다 짧으면 무조건 불일치
            cout << "NE" << '\n';
            continue;
        }

        // 파일명에서 접두사와 접미사 확인
        if (filename.substr(0, prefix.size()) == prefix &&
            filename.substr(filename.size() - suffix.size()) == suffix) {
            cout << "DA" << '\n';
        } else {
            cout << "NE" << '\n';
        }
    }

    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명.

• 핵심 알고리즘:
  • 패턴 문자열을 '*' 기준으로 분리하여 접두사(prefix)와 접미사(suffix)를 추출합니다.
  • 각 파일명에 대해 접두사와 접미사가 일치하는지 검사합니다.
• 구현 세부사항:
  • 패턴 문자열의 '*'를 기준으로 앞부분과 뒷부분을 추출합니다.
  • 각 파일명이 패턴의 접두사와 접미사를 포함하는지 확인합니다.
  • 파일명이 패턴보다 짧으면 즉시 "NE"를 출력합니다.
• 시간 복잡도 분석:
  • 패턴 분리: O(|pstr|), 여기서 |pstr|은 패턴 문자열의 길이입니다.
  • 파일명 확인: 각 파일명에 대해 O(|filename|) 연산이 수행되므로 총 시간 복잡도는 O(n ⋅ m)입니다. 여기서 n은 파일명 개수, m은 파일명의 평균 길이입니다.

---

결과

입력된 파일명 각각에 대해 패턴과 일치 여부를 정확히 판단하며, 결과를 출력합니다.

해당 문제에 대한 다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!