[ baekjoon ] 문자열 복사 2195번 ( python )

문제

백준 2195 문자열 복사 풀이 ( 파이썬 )

https://www.acmicpc.net/problem/2195

2195번: 문자열 복사

 

풀이

먼저 s에 대하여 각 문자에 인덱스를 저장하는 dict(자바에서는 Hashmap)을 선언하고 각 인덱스에서 부터 시작하여 같은 부분의 길이가 긴 temp길이를 찾아 구하고 index를 옮겨준다.

 

처음에 이 풀이를 생각했을 때

이렇게 겹치는 부분에 대한 예외가 있을거라고 생각했지만 어떤순서로 진행하든 copy함수를 호출하는 수는 같기 때문에

상관없었다.

s=input()
p=input()

char=dict()

# 각 문자에 대한 index 저장
for i in range(len(s)):
    char[s[i]]=char.get(s[i],[])+[i]

index=0
answer=0
len_s=len(p)

# 결국 이 while문을 몇 번이나 돌았나? 가 문제의 정답이 된다.
while index<len_s:
    arr=char[p[index]]

    cnt=0

    # 가장 같은 부분이 긴 부분 찾기
    for i in range(len(arr)):
        idx=arr[i]
        temp=0
        temp_index=index
        while idx<len(s) and temp_index<len_s:
            if s[idx]==p[temp_index]:
                idx+=1
                temp_index+=1
                temp+=1
            else:
                break
        cnt=max(cnt,temp)
        
    
    answer+=1
    index+=cnt
    

print(answer)