문자열 s와 쿼리 목록 Q가 주어졌다고 가정해 보겠습니다. 각 쿼리 Q[i]는 쌍 (l, r)을 담고 있으며, 우리는 s의 l번째부터 r번째까지 잘라낸 부분 문자열과 유사한 부분 문자열(s의 x번째부터 y번째까지)이 전체에서 몇 개나 되는지 찾아야 합니다.
두 문자열 s와 t가 유사하다고 판단되는 조건은 다음과 같습니다.
두 문자열의 길이가 서로 같아야 합니다.
모든 인덱스 쌍 (i, j)에 대해, s[i]와 s[j]가 같다면 t[i]와 t[j]도 반드시 같아야 하고, 반대로 s[i]와 s[j]가 다르다면 t[i]와 t[j]도 서로 달라야 합니다. 즉, 한 문자열의 문자 대응 관계가 다른 문자열에 그대로 성립해야 합니다.
예를 들어 입력이 s = "hjhhbcbk", Q = [(1,2), (2,4)]라면 출력은 [6, 1]이 됩니다. 그 이유는 다음과 같습니다.
- 첫 번째 쿼리 (1,2)에 대해 유사한 부분 문자열은 "hj", "jh", "hb", "bc", "cb", "bk"로 총 6개입니다.
- 두 번째 쿼리 (2,4)에 대해 유사한 부분 문자열은 "jhh" 하나뿐입니다.
해결 접근 방법
이 문제를 해결하기 위해 다음 단계를 따릅니다.
지문(fingerprint) 값을 저장할 빈 리스트 fp를 준비합니다.
calc_fingerprint()함수를 정의합니다. 이 함수는 문자열 s를 받아 각 문자에 처음 등장한 순서대로 고유 번호를 부여한 뒤, 그 번호들을 이어 붙인 정수를 반환합니다. 예를 들어 "aba"는 "010"이 됩니다. 이렇게 하면 문자 패턴 구조만 남게 되어 동형 여부를 숫자만으로 빠르게 비교할 수 있습니다.메인
solve()함수에서는 먼저 문자열 길이가 10보다 큰 경우, 가능한 모든 길이 10짜리 부분 문자열에 대해 지문을 미리 계산해 fp에 저장해 둡니다.각 쿼리 (a, b)에 대해 다음을 수행합니다.
- s1 := s[a-1:b]로 기준 부분 문자열을 만듭니다.
- 카운터 k := 0으로 초기화합니다.
- 시작 위치 i를 0부터 len(s)-(b-a)-1까지 이동시키며:
- 쿼리 구간 길이가 10보다 크고 fp[a-1]과 fp[i]가 다르면, 구조 자체가 다르므로 해당 후보는 건너뜁니다. 이 필터링 덕분에 불필요한 문자 단위 비교를 크게 줄일 수 있습니다.
- s2 := s[i : i+(b-a)+1]로 비교 대상 부분 문자열을 만듭니다.
- 두 문자열이 동형인지 확인하고, 유사하다면 k를 1 증가시킵니다.
- 각 쿼리가 끝날 때마다 k를 결과 리스트 ret에 추가합니다.
모든 쿼리 처리가 끝나면 ret을 반환합니다.
구현 예제
아래 구현을 통해 더 잘 이해해 보겠습니다.
fp = []
def calc_fingerprint(s):
dict = {s[0]: 0}
fp = "0"
j = 1
for i in range(1, len(s)):
if s[i] not in dict:
dict[s[i]], j = j, j+1
fp += str(dict[s[i]])
return int(fp)
def solve(s, Q):
if len(s) > 10:
for i in range(0, len(s)-10):
fp.append(calc_fingerprint(s[i: i+10]))
ret = []
for i in range(len(Q)):
a, b = Q[i]
s1 = s[a-1:b]
k = 0
for i in range(len(s)-(b-a)):
if b-a > 9 and fp[a-1] != fp[i]:
continue
dict = {}
s2 = s[i:i+(b-a)+1]
for i in range(b-a+1):
if s2[i] not in dict:
if s1[i] in dict.values(): break
dict[s2[i]] = s1[i]
if dict[s2[i]] != s1[i]: break
else:
k += 1
ret.append(k)
return ret
s = "hjhhbcbk"
Q = [(1,2), (2,4)]
print(solve(s, Q))입력
"hjhhbcbk", [(1,2), (2,4)]
출력
[6, 1]