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?")
