[SWEA] 3143. 가장 빠른 문자열 타이핑 - Python

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV_65wkqsb4DFAWS 

SW Expert Academy

 

< 📝 문제 >

어떤 문자열 A를 타이핑하려고 한다.

그냥 한 글자씩 타이핑 한다면 A의 길이만큼 키를 눌러야 할 것이다.

여기에 속도를 조금 더 높이기 위해 어떤 문자열 B가 저장되어 있어서 키를 한번 누른 것으로 B전체를 타이핑 할 수 있

 

다. 이미 타이핑 한 문자를 지우는 것은 불가능하다.

예를 들어 A=”asakusa”, B=”sa”일 때, 다음 그림과 같이 B를 두 번 사용하면 5번 만에 A를 타이핑 할 수 있다.

A와 B가 주어질 때 A 전체를 타이핑 하기 위해 키를 눌러야 하는 횟수의 최솟값을 구하여라.

< ❓ 생각 >

타이핑 수 : len(A)-(B가 A에 속한 횟수)*(len(B)-1)

 

앞에서 부터 덩어리로 비교

 1) 속한다면 -> 속한 횟수 +1, 비교위치 +len(B)

 2) 속하지 않는다면 -> 비교위치 +1

< 💻 코드 >

# T : 테스트 케이스 수
T = int(input())
for tc in range(1,T+1):
    A, B = map(str,input().split())
    # 타이핑 수 : len(A)-(B가 A에 속한 횟수)*(len(B)-1)
    # cnt = (B가 A에 속한 횟수)
    cnt = 0
    # A의 인덱스 (비교 위치)
    i = 0
    while i <= len(A)-len(B):
        # 속한다면 - > 속한 횟수 +1, 비교위치 +len(B)
        if A[i:i+len(B)] == B:
            cnt += 1
            i += len(B)
        # 속하지 않는다면 - > 비교위치 +1
        else:
            i += 1
    result = len(A) - cnt * (len(B)-1)

    print(f'#{tc} {result}')