99클럽 코테 스터디 8일차 TIL + 한국이 그리울 땐 서버에 접속하지(백준 9996번)

✅ 오늘의 학습 키워드

• 문자열 처리
• 패턴 매칭 알고리즘
• substr(), find()

---

✅ 공부한 내용

- 문제 요약

(백준 문제 링크: https://www.acmicpc.net/problem/9996)

 

이 문제는 특정 패턴과 파일 이름이 일치하는지 확인하는 패턴 매칭 알고리즘을 구현해야한다.

패턴은 알파벳 소문자와 별표(*) 하나로 이루어져 있다.

파일 이름이 패턴과 일치하려면 별표(*)를 알파벳 소문자로 이루어진 임의의 문자열(빈 문자열 포함)로 변환했을 때 파일 이름과 같아야 한다.

프로그램은 각 파일 이름이 패턴과 일치하는지 여부를 "DA"(true) 또는 "NE"(false) 로 출력해야 한다.

- 풀이 로직

1. main() 함수의 경우

- 첫 번째 줄에서 파일의 개수 N을 입력

- 두 번째 줄에서 패턴을 입력

- 다음 N개의 줄에서 파일 이름들을 입력 각 파일 이름이 패턴과 일치하는지 확인하고 결과를 출력

- 패턴과 일치하면 "DA"를 출력

- 패턴과 일치하지 않으면 "NE"를 출력

 

2. matchPattern() 함수의 경우

- 패턴에서 *의 위치를 찾는다.

- * 앞의 문자열을 앞부분(prefix)로, * 뒤의 문자열을 뒷부분(suffix)로 나누기

- 파일 이름이 앞부분(prefix)으로 시작하고, 뒷부분(suffix)으로 끝나는지 확인( + 빈 문자열인지 아닌지도 확인)

- 파일 이름의 길이가 충분한지도 확인 (파일 이름의 길이가 앞부분, 뒷부분의 길이 합보다 작으면 안됌)

- 위의 모두 조건을 만족하면 true 반환

---

✅ 오늘의 회고

- 😳 어떤 문제가 있었고, 나는 어떤 시도를 했는지

오늘은 패턴 매칭 알고리즘을 구현하면서 문자열 처리에 관한 실수를 했다.
패턴을 '*' 기준으로 앞부분(prefix)과 뒷부분(suffix)으로 나누는 과정에서처음에는 단순히 패턴을 분리하는 데만 집중하다보니 suffix에서 다음과 같이 작성했다.

// 처음 작성한 코드
string prefix = pattern.substr(0, star);
string suffix = pattern.substr(star); // << 요기가 문제가 있는 부분

이렇게 작성했을 때 당연히 * 문자 자체가 포함되어서 잘리는 문제가 생겼다. star + 1로 해줘야했는데.. 하핳...(조심해! 퍽-)

- 🤔 어떻게 해결했는지

substr() 함수의 시작 인덱스를 *의 위치가 아닌 * 다음 위치로 수정했습니다.

// 수정한 코드
string prefix = pattern.substr(0, star);
string suffix = pattern.substr(star + 1); // '*' 다음 위치부터 시작

star + 1로 변경함으로써 * 문자 자체는 제외하고 그 뒤에 오는 문자열만 suffix로 추출할 수 있었다.

- 🤩 무엇을 새롭게 알았는지

• C++ string 클래스의 메소드들(find, substr)을 활용한 문자열 처리를 할때 인덱싱을 조심하자.

---

✅ 전체 코드

#include <iostream>
#include <string>
#include <vector>

using namespace std;


// '*' 위치를 찾아 패턴을 앞부분(prefix)과 뒷부분(suffix)으로 나눈다.
bool matchPattern(string pattern, string filename){

    // '*' 위치 찾기
    int star = pattern.find('*');

    // '*' 를 기준으로 패턴의 앞부분과 뒷부분 자르기
    string prefix = pattern.substr(0, star);
    string suffix = pattern.substr(star + 1);

    // 파일 이름의 길이가 충분한지 확인
    if (filename.length() < prefix.length() + suffix.length()) {
        return false;
    }

    // 파일 이름이 앞부분으로 시작하는지 확인
    if (filename.substr(0, prefix.length()) != prefix) {
        return false;
    }

    // 뒷부분(suffix)이 빈 문자열인지 아닌지 확인 && 파일 이름이 뒷부분으로 끝나는지 확인
    if (suffix.length() > 0 && filename.substr(filename.length() - suffix.length()) != suffix) {
        return false;
    }

    return true;
}

int main() {
    int N;
    string pattern;

    cin >> N;
    cin >> pattern;

    vector<string> filenames(N);
    for(int i = 0; i < N; i++) {
        cin >> filenames[i];
    }

    for(int i = 0; i < N; i++) {
        if(matchPattern(pattern, filenames[i])) {
            cout << "DA" << '\n';
        }
        else {
            cout << "NE" << '\n';
        }
    }

    return 0;
}