문자열 컨테이너가 주어지면 각 원소 A, B에 대해 swappable(A, B) => ((AB) == (BA))인지 확인하래
AB = BA만 두고 보면 아무것도 못함
쪼개기 ㄱㄱ
우선 len(A) = len(B)면 A = B여야함은 자명함
그럼 둘 중 긴 놈을 A, 짧은 놈을 B로 두면(len(A) > len(B))
C = A[:len(B)], D = A[len(B):]로 쪼개기 가능
A = CD가 되겠지(len(C) = len(B))
그럼
AB = BA는
CDB = BCD가 되는데
len(C) = len(B)이므로
C = B임
남는건 DB = BD가 되니까 재귀적으로
def swappable(A, B):
if len(A) == len(B): return A == B
C = A[:len(B)]
D = A[len(B):]
return C == B and swappable(B, D)
이렇게 생겨먹었네
그럼 탑다운에서 바텀업으로 바꾸면 모든 swappable한 문자열쌍을 생성 가능함
A == B인 기저 swappable(S, S)에서 시작해보면
(C == B and swappable(B, D))에서 B = S, D = S 였을테고
B = D = C = S니까
A = SS임
swappable(S, S) => swappable(SS, S)
즉 반복되는 경우만 가능하고 다른 예외는 존재할 수 없음
빈 문자열을 제외한 문자열들은 A가 반복되는 꼴이어야하니 len(A)는 gcd(나머지 문자열 길이...) 여야함
아무거나 앞부분 gcd(나머지 문자열 길이...)길이만큼 잘라서 A로 두고 반복되는지 보면 끝이겠지?
예 뭐 제출탭에 선형 풀이 있는거 보면 아마 같은 풀이일텐데
아침에 오랜만에 구경왔다가 문제 있길래 풀어봤습니다
py왜 last() 없냐 max()쓰긴 흐름이 이상하고
sum()도 add function 못넣고
에잉 ㅅㄱㅅㄱ
댓글 0