백준 17413 - 단어 뒤집기 2(C++)

문제 링크입니다. https://www.acmicpc.net/problem/17413

17413번: 단어 뒤집기 2

주어진 문자열을 뒤집는 문제입니다.

 

까다로운 조건이 있는데 확인해보면

1. < >안의 문자는 뒤집어지지 않습니다.

2. 스페이스를 기준으로 뒤집어집니다.

  2-1. < >안에 스페이스가 있다면 뒤집지 않습니다.

3. 문자열의 길이가 100000이기에 문자열을 확인하는 과정에서 뒤집으면 시간초과의 가능성이 있습니다.

 

위의 조건만 신경쓰면 됩니다.

 

따라서, 저는 2개의 문자열로 구분해서 저장했습니다.

1. < >안에 있는 문자열

2. < >안에 없는 문자열(스페이스를 기준으로 나눠지는 문자열)

 

입력된 문자열을 확인하는 과정에서 '>' 가 나온다면 '<'로 시작되는 문자부터 저장하고 있었다는 의미입니다.

따라서 해당 문자열에는 1이라는 정수값을 부여함으로서 뒤집지 않는 문자열임을 저장해줍니다.

 

' '으로만 구분되는 문자열이라면 0이라는 정수값을 부여함으로서 나중에 뒤집어줍니다.

 

' '와 '<', '>'으로만 구분한다면 < > 안에 존재하는 ' '을 구분하지 못하게 됩니다.

따라서 변수 하나를 만들어 '<' 부터 입력되었을 때, ' '가 입력되어도 뒤집지 못하게만 해주면 됩니다.

 

자세한 것은 코드를 참고해주세요.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>

using namespace std;

char arr[100001];
string ans;
vector<pair<string, int>> Re;

int main(){
    cin.tie(0);
    cout.tie(0);
    cin.getline(arr, 100001);
    string x = "";
    bool connect = false;
    for(int i = 0; i < strlen(arr); i++){
        if(arr[i] == '<'){
            Re.push_back({x, 0});
            x = "";
            x += arr[i];
            connect = true;
        }
        else if(arr[i] == '>'){
            x += arr[i];
            Re.push_back({x, 1});
            x = "";
            connect = false;
        }
        else if(arr[i] == ' ' && !connect){
            Re.push_back({x, 0});
            Re.push_back({" ", 0});
            x = "";
        }
        else x += arr[i];
    }
    if(x.size() > 0) Re.push_back({x, 0});
    for(int i = 0; i < Re.size(); i++){
        if(Re[i].second == 0){
            for(int j = Re[i].first.size() - 1; j >= 0; j--){
                cout << Re[i].first[j];
            }
        }
        else{
            for(int j = 0; j < Re[i].first.size(); j++){
                cout << Re[i].first[j];
            }
        }
    }
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요