[C++] 백준 BOJ 9935 문자열 폭발

문제링크 : https://noj.am/9935

요즘 알고리즘 테스트 문제들이 파싱 문제들이 하도 많이 나와서 연습해볼겸 별 의미는 없지만 string stream을 사용하여 풀어보았다.

string stream을 통하여 입력된 문자열이 폭발 문자열의 '마지막 문자'에 해당할 경우 이전에 입력되었던 문자열이 폭발 문자열과 일치하는지 체크하는 방법으로 풀이했다. 본 풀이법은 스택을 사용한 풀이법이라 할 수 있다.

예제에서는 "C4"가 폭발 문자열이다.

아래의 조건에서 '4'를 찾았다면 문자열 탐색이 실행된다.

if (s == bomb.back())

먼저 idx 변수를 폭발 문자열 크기만큼 뺀 인덱스로 초기화 시켜준다.

폭발 문자열의 맨 앞인 'C'에 해당하는 값이다.

int idx = result.size() - bomb.size();
// 인덱스가 0보다 작을 수 없음
if (idx < 0) continue;

idx를 하나씩 늘려가면서 폭발 문자열 탐색을 수행해준다.

// 변수 설정
bool del = true;
int size = bomb.size();
// 폭발 문자열 탐색
for(int i = 0; i < size; i++) {
    // 하나라도 다른 문자 나오면 탈출
    if (result[idx++] != bomb[i]) {
        del = false;
        break;
    }
}

C++의 string 클래스는 컨테이너 형태이기 때문에 push_back() 함수로 글자 제거가 가능하다.

// 문자열 제거
if(del) while(size--) result.pop_back();

// BOJ 9935 문자열 폭발
#include <iostream>
#include <string>
#include <sstream>
 
using namespace std;
 
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("../input.txt", "r", stdin);
 
    string input; // 입력 문자열
    string bomb;  // 폭발 문자열
    string result;
    cin >> input >> bomb;
    stringstream ss(input);
 
    char s; // 문자열 탐색을 위한 변수
    while (ss >> s) {
        result.push_back(s);
        // 입력 문자가 bomb의 끝 문자랑 같으면 실행
        if (s == bomb.back()) {
            int idx = result.size() - bomb.size();
            // 인덱스가 0보다 작을 수 없음
            if (idx < 0) continue;
            // 변수 설정
            bool del = true;
            int size = bomb.size();
            // 폭발 문자열 탐색
            for(int i = 0; i < size; i++) {
                // 하나라도 다른 문자 나오면 탈출
                if (result[idx++] != bomb[i]) {
                    del = false;
                    break;
                }
            }
            // 문자열 제거
            if(del) while(size--) result.pop_back();
        }
    }
    if(result.size() == 0)
        cout << "FRULA";
    else
        cout << result;
 
    return 0;
}