문제 링크

https://www.hackerrank.com/challenges/append-and-delete

주의 사항

appendAndDelete has the following parameter(s):

string s: the initial string
string t: the desired string
int k: the **exact** number of operations that must be performed

• 여기서 int k가 exact한 연산 횟수였다..
• exact를 확인하지 못해서 문제 풀이를 엄청 헤맸다..

문제 풀이

# 틀린 풀이

def appendAndDelete(s, t, k):
    if s == t:
        return 'Yes'
    tmp = 0
    for i in range(len(s)-1, -1, -1):
        tmp += 1
        if s[:i] == t[:i]:
            break
    tmp += len(t)-len(t[:i])
    if k >= tmp:
        return 'Yes'
    else:
        return 'No'

• k번 이하의 연산으로 문제를 해결하라는 건 줄 알고 풀었던 풀이..

# 정답 풀이

def appendAndDelete(s, t, k):
    cnt = 0

    for i, j in zip(s, t):
        if i == j:
            cnt += 1
        else:
            break
            
    total_len = len(s)+len(t)
    
    if ((2*cnt + k >= total_len) and (total_len%2 == k%2)) or total_len <= k:
        return 'Yes'
    else:
        return 'No'

• 변수 설명
  cnt : s와 t가 앞에서부터 겹치는 문자의 길이
  2*cnt + k : 만들 수 있는 최대 문자 길이

  • 겹치는 문자는 지웠다 썼다 해야하므로 *2

• 조건 설명
  (2*cnt + k >= total_len) : 최대로 만들 수 있는 문자의 길이가 기존 두 문자 길이의 합보다 크거나 같아야 함
  (total_len%2 == k%2) : exact하게 동일한 연산을 해야하므로 k와 total_len의 홀짝이 동일해야 함

  • 여기서 k대신 2*cnt+k를 써도 되는데 2*cnt가 짝수 이므로 생략 가능

  total_len <= k : 전체 길이가 k보다 작거나 같은 경우

  • 주어진 연산 2번에서 '공백일 경우 지워도 공백이다'라는 조건 활용할 경우 k에 어떤 수가 주어져도 k에 맞춰서 조절 가능