[Programmers] #181864 - 문자열 바꿔서 찾기 [Java][C++][Python]

문제 링크

---

1. 아이디어

문자열 myString의 각 문자에 대해 "A"와 "B"를 바꾼 후 pat를 부분 문자열로 갖는지 판단하는 문제로 문자 변환을 일괄로 처리해서 바꿨던 문자를 또 바꾸지만 않게 주의하면 된다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N \times M)$	$O(N)$

($N$ = myString의 길이, $M$ = pat의 길이. 시간 $O(N \times M)$은 Java·C++의 표준 라이브러리 탐색(contains/find)이 나이브 비교라서이고, Python은 in이 two-way 알고리즘이라 $O(N + M)$. 공간은 Java·Python이 변환한 새 문자열을 만들어 $O(N)$, C++는 값으로 받은 사본을 제자리에서 변환하므로 $O(1)$)

---

3. 코드

풀이 [Java][C++][Python]

class Solution {
    public int solution(String myString, String pat) {
        char[] arr = myString.toCharArray();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (arr[i] == 'A') ? 'B' : 'A';
        }

        return new String(arr).contains(pat) ? 1 : 0;
    }
}

#include <bits/stdc++.h>
using namespace std;

int solution(string myString, string pat) {
    for (char& c : myString) {
        c = (c == 'A') ? 'B' : 'A';
    }

    return myString.find(pat) != -1;
}

def solution(myString, pat):
    s = "".join("B" if c == "A" else "A" for c in myString)
    return int(pat in s)

---