[Python 3] BOJ 17452 Christmalo.win

 

문자열들의 앞과 뒤를 잘라서, 같은 알파벳이 있으면 서로 연결시킬 수 있다.

이 때, 자르는 알파벳들의 수가 최소가 되게끔 해야한다.

 

따라서, christma(s), (h)alloween을 통해 각각 s와 h를 지우면 연결을 할 수 있는 셈이다.

 

여기서 두 개의 문자열을 보고 하나하나 비교를 하게 되면, 10만개 중에 두개를 고르는, 10만 C 2 개의 연산을 해야하고, 이는 무조건적으로 TLE를 받게 된다.

 

문제의 포인트는 결국 '알파벳'을 기준으로 연결한다는 점이다.

a부터 z까지의 알파벳이 왼쪽에서 언제 제일 빨리 나오는지, 오른쪽에서 언제 제일 빨리 나오는지를 저장한다. 

(left,right)

각 string을 돌면서, string에서 a부터 z까지 각 알파벳이 왼쪽에서 언제 제일 빨리 나오는지, 오른쪽에서 제일 빨리 나오는지를 저장한다.

(templeft, tempright)

 

이렇게 두 개의 리스트를 분리한 이유는, left와 right을 바로바로 update해버리면, 연산을 할 때 같은 문자열의 left와 right을 함께 연산해서, 실제로 두 개의 문자열을 가지고 왼쪽, 오른쪽을 자르는게 아니라 한 문자열을 두번 중복해서 사용하게 될 수도 있다. 따라서 먼저 templeft, tempright에 저장해두고, 나중에 update하는 방식을 채택했다.

 

n=int(input())
data=list(input() for _ in range(n))
left=list(1e10 for _ in range(26))
right=list(1e10 for _ in range(26))
answer=1e10
for i in data:
    templeft=[1e10 for _ in range(26)]
    tempright=[1e10 for _ in range(26)]
    leng=len(i)
    for j in range(leng):
        k=leng-j-1
        templeft[ord(i[j])-ord('a')]=min(templeft[ord(i[j])-ord('a')],j)
        tempright[ord(i[j])-ord('a')]=min(tempright[ord(i[j])- ord('a')],k)
    for j in range(26):
        if templeft[j]!=1e10 and right[j]!=1e10:
            answer=min(templeft[j]+right[j],answer)
        if tempright[j]!=1e10 and left[j]!=1e10:
            answer=min(tempright[j]+left[j],answer)
        left[j]=min(left[j],templeft[j])
        right[j]=min(right[j],tempright[j])
if answer==1e10:
    print(-1)
else:
    print(answer)