[프로그래머스][C++] 문자열 바꿔서 찾기

문자열 바꿔서 찾기

문제 링크

문자열 바꿔서 찾기

분석

myString의 문자 중 ‘A’는 ‘B’로, ‘B’는 ‘A’로 바꾸어 새로운 문자열을 생성해야합니다.

새로운 문자열에서 pat과 같은 부분 문자열이 존재하는지 확인해야합니다.

즉, myString의 문자를 변경한 후, 결과 문자열에 pat이 포함되어 있는지 확인하는 문제입니다.

풀이

#include <string>

using namespace std;

int solution(string myString, string pat) {
    int answer = 0;
    
    // 문자를 변경하는 반복문
    for (int i = 0; i < myString.length(); ++i)
    {
        if (myString[i] == 'A')
        {
            myString[i] = 'B';
        }
        else
        {
            myString[i] = 'A';
        }
    }
    
    // 부분 문자열을 검색한다.
    if (myString.find(pat) != string::npos)
    {
        answer = 1;
    }
    
    return answer;
}

성능 요약

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

• 문자를 변경하는 반복문 $O(n)$
• 부분 문자열을 검색하는 함수 string::find $O(n * m)$
• $O(n) + O(n * m)$

공간 복잡도는 추가적인 공간을 사용하지 않기 때문에 $O(1)$입니다.

테스트 성능

테스트 1 〉 통과 (0.01ms, 4.15MB)
테스트 2 〉 통과 (0.01ms, 3.67MB)
테스트 3 〉 통과 (0.01ms, 4.14MB)
테스트 4 〉 통과 (0.01ms, 4.05MB)
테스트 5 〉 통과 (0.01ms, 4.14MB)
테스트 6 〉 통과 (0.01ms, 3.66MB)
테스트 7 〉 통과 (0.01ms, 3.67MB)