AI slop

서브태스크 1

$N=2$이면 길이가 $2$인 부분문자열은 문자열 전체뿐이다. 따라서 $S$가 $\texttt{ai}$와 같은지 비교하면 된다. 각 테스트 케이스의 시간 복잡도와 추가 공간 복잡도는 모두 $O(1)$이다.

서브태스크 2

문자열에서 서로 이웃한 두 문자를 차례대로 확인한다. 앞 문자가 $\texttt{a}$이고 뒤 문자가 $\texttt{i}$인 위치가 하나라도 있으면 AI slop을 출력한다. 그런 위치가 없으면 Human made를 출력한다.

길이가 $2$인 모든 부분문자열은 이웃한 두 문자로 이루어진다. 따라서 이 방법은 $\texttt{ai}$가 부분문자열로 존재하는지를 정확히 판별한다. $N=1$이면 확인할 두 문자가 없으므로 Human made를 출력한다.

각 테스트 케이스의 시간 복잡도는 $O(N)$이고, 문자열 저장에 $O(N)$ 공간을 사용한다. 문자열을 저장한 뒤 판별하는 데 필요한 추가 공간은 $O(1)$이다. 전체 시간 복잡도는 $O(T+\sum N)$이다.

문자열 검색 기능을 사용해 $\texttt{ai}$의 포함 여부를 확인해도 된다.

Solution written by GPT6