[SWEA][D4][#03143] 가장 빠른 문자열 타이핑

출처

• SW Expert Academy

학습용 포스트입니다. 본 포스트가 문제가 될 시 수정 또는 삭제하겠습니다.

문제

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

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

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

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

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

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

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스마다 첫 번째 줄에 두 문자열 A, B가 주어진다. A의 길이는 1이상 10,000이하, B의 길이는 1이상 100이하이다.

출력

각 테스트 케이스마다 A 전체를 타이핑 하기 위해 키를 눌러야 하는 횟수의 최솟값을 출력한다.

예제

입력

2
banana bana
asakusa sa

출력

#1 3
#2 5

My Sol A : 완전탐색 사용

T = int(input())
for tc in range(T):
    t, p = input().split()
    tl, pl = len(t), len(p)
    ti, pi = 0, 0

    cnt = 0
    while ti<tl and pi<pl:
        if t[ti] != p[pi]:
            ti -= pi
            pi = -1
        ti += 1
        pi += 1

        if pi == pl:
            cnt += 1
            pi = 0

    ans = tl - (pl-1)*cnt
    print(f'#{tc+1} {ans}')

역시 완전탐색을 사용하여 일치하는 부분의 개수를 세고 이를 이용해 차이와 개수를 곱한 값을 전체 텍스트의 길이에서 빼주면 답이 된다.

My Sol B : replace 메서드 사용

T = int(input())
for tc in range(T):
    t, p = input().split()
    ans = t.replace(p,'.')
    print(f'#{tc+1} {len(ans)}')

어차피 뭉쳐있는 입력도 하나의 입력으로 따져지므로 replace() 메서드를 이용하여 길이를 계산하면 된다. 너무 쉽지만 알고리즘을 사용하는 방법이 아니고, replace메서드 자체도 내부적으로는 탐색의 과정을 거치기 때문에 알고리즘 공부를 하는동안은 사용을 지양해야 한다.

하지만 로직 자체는 알아두면 좋을 것 같아서 적어둔다.

결과

PASS