2019 KCPC acronym

2019 KCPC KCPC는 무엇의 약자일까? (신입생 부문 C번) 코드 제출 url

문자열 A를 B로 압축할 수 있는지 여부를 판단하는 함수를 만들면 쉽습니다.

이 함수는 시간복잡도 O(len(A)+len(B))로 해결할 수 있습니다.

예를 들어보겠습니다. KACAPACA를 KCPCP로 압축할 수 있는지 어떻게 찾을 수 있을까요?

KACAPACA에서 가장 왼쪽에 있는 K를 찾습니다.

ACAPACA에서 가장 왼쪽에 있는 C를 찾습니다.

APACA에서 가장 왼쪽에 있는 P를 찾습니다.

…

A에서 가장 왼쪽에 있는 P를 찾습니다.

이제 보이시나요? 처음부터 다시 찾을 필요가 없습니다. 찾았던 다음 위치에서 검색을 이어나가면 되기 때문에 O(len(A)+len(B))를 만족합니다.

def kcpc(aft, bef):
    a_idx=0; b_idx=0
    al=len(aft); bl=len(bef)
    while a_idx<al:
        while b_idx<bl and aft[a_idx]!=bef[b_idx]:
            b_idx=b_idx+1
        if b_idx>=bl:
            return False
        a_idx=a_idx+1
        b_idx=b_idx+1
    return True

if __name__=='__main__':
    aft=input()
    bef=input()
    if kcpc("KCPC",bef) and kcpc(aft,bef):
        print("KCPC!")
    else:
        print("KCPC?")