백준(BOJ) 9342 염색체 C++ 풀이

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

9342번: 염색체

문제 풀이에 이용된 알고리즘: 구현 및 정규식

 

어떤 문자열이 입력되었을 때 일련의 규칙을 만족하는 문자열인지 파악하기 위해, 다량의 if-else문으로 문제를 풀이했다. 문자열의 인덱스 0부터 하나씩 증가시키며, 특히 중간에 A, F, C 등이 1개 이상 등장할 수 있을 때는 새로운 문자가 등장할 때까지 인덱스를 증가시키고, 새롭게 등장한 그 문자가 규칙에 맞는 지 확인하는 방식으로 문제를 풀었다. 

 

하지만 모든 테스트 케이스가 맞았음에도 틀림 판정을 받았고, 질문 탭에도 질문이 전혀없어서 문제 난이도가 실버4인 것에 비해서 어렵다는 느낌을 받았고 접근 방법을 바꾸게 되었다.

 

고민하던 중, 알고리즘 설계라는 학과 수업 시간에 접했던 정규식을 이용한 패턴 매칭 개념이 생각났다. 이론적으로는 어떤 문자열의 정규식과 그에 대응되는 비결정적 패턴 매칭 장치를 그리고 매칭을 수행했지만 실제로 프로그램으로 작성한 적이 없었는데, C++의 경우 regex라는 헤더를 쓰면 굉장히 손쉽게 구현할 수 있었다.

 

먼저, 문제에서 주어진 규칙들을 만족하는 문자열을 정규식 형태로 표현하고, regex_match라는 함수를 이용하여, 입력 받은 문자열과 정규식이 일치하는지 확인하면 된다.

 

정규식 형태 표현에 이용되는 규칙은 주석으로 간단히 작성하였다.

 

/* BOJ 9342 염색체 */
/* 정규식 regex matching 이용 */
#define _CRT_SECURE_NO_WARNINGS
 
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <string.h>
#include <regex>
 
#define endl '\n'
 
using namespace std;
 
typedef long long ll;
 
int T;
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    //freopen("input.txt", "r", stdin);
 
    // [A-F]는 A~F를 찾는다는 의미
    // X?는 X가 0회 또는 1회 등장함을 의미
    // X+는 X가 1회 이상 반복됨을 의미
    regex r(R"(^[A-F]?A+F+C+[A-F]?$)");
 
    cin >> T;
    for (int t = 1; t <= T; t++)
    {
        string str;
        cin >> str;
        if (regex_match(str, r)) // 정규식을 이용한 패턴 매칭
            cout << "Infected!" << endl;
        else cout << "Good" << endl;
    }
 
    return 0;
}