[알고리즘 풀이 분석] BOJ 17413 단어 뒤집기 2

오늘도 문자열 문제 연습을 해 보았다. 오늘 푼 문제는 BOJ 17413 단어 뒤집기 2 이다!

BOJ 17413 단어 뒤집기 2

문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다.

먼저, 문자열 S는 아래와과 같은 규칙을 지킨다.

1. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('<', '>')로만 이루어져 있다.
2. 문자열의 시작과 끝은 공백이 아니다.
3. '<'와 '>'가 문자열에 있는 경우 번갈아가면서 등장하며, '<'이 먼저 등장한다. 또, 두 문자의 개수는 같다.

태그는 '<'로 시작해서 '>'로 끝나는 길이가 3 이상인 부분 문자열이고, '<'와 '>' 사이에는 알파벳 소문자와 공백만 있다. 단어는 알파벳 소문자와 숫자로 이루어진 부분 문자열이고, 연속하는 두 단어는 공백 하나로 구분한다. 태그는 단어가 아니며, 태그와 단어 사이에는 공백이 없다.

입출력

[입력]
첫째 줄에 문자열 S가 주어진다. S의 길이는 100,000 이하이다.

[출력]
첫째 줄에 문자열 S의 단어를 뒤집어서 출력한다.

나의 풀이

단어가 태그 안에 있을때와 없을때 공백 처리를 따로 해 주어야 하는 문제라고 판단해 알고리즘을 짰지만 그럴 필요가 없었고 태그인지 아닌지만 구분 해 주면 되는 문제였다.

왼쪽 태그 괄호 <를 만나면 > 를 만날 때 까지 그대로 문자열을 옮겨 적고 단어가 시작되면 끝날 때 까지 stack 에 담아 역순으로 출력해 임시 문자열 temp 를 만든다.

이후 temp 를 공백을 기준으로 나누어 자르고 뒤에서부터 역순으로 붙여주면 간단하게 해결된다.

이런 문제의 경우 여러 케이스를 복잡하게 나누는 것 보다 공통된 부분을 잘 파악해서 단순하게 해결하는게 정답률이 더 높은 것 같다. 여러 케이스를 나누다 보면 꼭 반례가 생기기 마련인,, 느낌 ,,?

코드

#include <iostream>
#include <string>
#include <stack>
#include <sstream>
#include <vector>

// boj 17413 단어 뒤집기2, 실버 3, 문자열
using namespace std;

string tokenize(string temp){
    string result = "";
    istringstream ss(temp);
    vector<string> tokens;
    string tk;

    while (getline(ss, tk, ' ')){
        tokens.push_back(tk);
    }

    for (int i = tokens.size()-1; i >=0 ; --i) {
        if (i<tokens.size()-1) result += " ";
        result += tokens[i];
    }

    return result;
}

string convertStr(string str){
    string result = "";
    int i = 0;

    stack<string> st;

    while (i<str.size()){
        if (str[i] == ' '){
            result += " ";
            i++;
            continue;
        }

        if (str[i] == '<'){
            while (str[i] !='>'){
                result += str.substr(i++, 1);
            }
            result += str.substr(i++, 1);
        }else{
            while (i<str.size() && str[i] != '<'){
                st.push(str.substr(i++, 1));
            }


            string temp = "";
            while (!st.empty()){
                temp += st.top();
                st.pop();
            }

            result += tokenize(temp);
        }
    }

    return result;
}

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

    string str;
    getline(cin, str);

    string answer = convertStr(str);
    cout<<answer;

    return 0;
}