[백준][C++] 17413번 단어 뒤집기 2

단어 뒤집기 2

문제 링크

단어 뒤집기 2

분석

이 문제는 문자열을 순회하며 특정 조건에 따라 문자를 뒤집거나 그대로 출력해야 하는 문제입니다.

입력으로 공백을 포함한 문자열들이 주어지며, 알파벳 소문자 및 숫자, <, >로 이루어진 단어들이 혼합돼있습니다.

문자열은 크게 두 가지 경우로 나뉩니다.

1. 태그 내부 <, >
   • <부터 >까지의 문자열은 그대로 출력합니다.
   • 태그 내부의 문자는 뒤집지 않습니다.
2. 태그 외부
   • 공백을 기준으로 문자열을 나눕니다.
   • 각 문자열을 뒤집어줍니다.

해당 조건에 맞춰 뒤집거나 뒤집지 않은 문자열들을 출력해야합니다.

풀이

#include <iostream>
#include <string>

int main()
{
	// 공백을 포함한 한 줄 전체 입력
    std::string InputStr;
    getline(std::cin, InputStr);

	// 최종 결과 문자열
    std::string Result;
    // 뒤집기 용도로 단어를 임시로 저장
    std::string Temp;

	// 현재 태그 내부인지 여부
    bool InTag = false;
	
	// 전체 문자열을 순회하는 반복문
    for (char C : InputStr)
    {
	    // 태그 시작
        if (C == '<')
        {
            // 태그 시작 전에 쌓아둔 단어가 있다면 뒤집어서 결과를 추가한다.
            for (int i = Temp.size() - 1; i >= 0; --i)
            {
                Result += Temp[i];
            }
                
            // 임시 문자열 초기화
            Temp.clear();
			
			// 태그 내부 상태로 변경
            InTag = true;
            
            // <는 그대로 출력
            Result += C;
        }
        // 태그 종료
        else if (C == '>')
        {
	        // 태그 외부 상태로 변경
            InTag = false;
            
            // >는 그대로 출력
            Result += C;
        }
	    // 태그 내부일 경우
        else if (InTag)
        {
	        // 태그 내부 문자는 그대로 출력
            Result += C;
        }
        // 태그 외부일 경우
        else
        {
	        // 공백을 만난 경우 단어의 끝
            if (C == ' ')
            {
                // 모아둔 단어 뒤집어서 결과에 추가
                for (int i = Temp.size() - 1; i >= 0; --i)
                    Result += Temp[i];
                    
                // 임시 문자열 초기화
                Temp.clear();

				// 공백 그대로 출력
                Result += ' ';
            }
            else
            {
	            // 일반 문자라면 나중에 뒤집기 위해 임시 문자열에 쌓아둔다.
                Temp += C;
            }
        }
    }

    // 문자열이 공백으로 끝나지 않을 경우을 위한 마지막 단어 처리
    for (int i = Temp.size() - 1; i >= 0; --i)
    {
        Result += Temp[i];
    }

    std::cout << Result << std::endl;
}

성능 요약

시간 복잡도는 $O(n)$입니다.

• 문자열 순회 $O(n)$
• 문자열 누적 $O(n)$
• 문자열 뒤집기 $O(n)$
• $O(n) + O(n) + O(n)$

공간 복잡도는 $O(l)$입니다.

• 입력 문자열을 저장하는 변수 $O(l)$
• 결과 문자열을 저장하는 변수 $O(l)$
• 임시 문자열을 저장하는 변수 $O(l)$

메모리: 2508 KB

시간: 4 ms