[HackerRank/C++] Append and Delete

문자열 s에서 문자열 t로 변환하고 싶으며 수정 규칙은 다음과 같다

 

1. 한번에 맨 끝의 문자를 지우거나, 맨 끝의 임의의 문자를 추가하는 것이 가능하다

 

2. 문자열이 하나도 없을때 지우는 행동은 아무결과 없음으로 처리된다

 

k번 만큼 문자열을 수정 할 때, s 문자열에서 t 문자열로 변환이 가능할지 확인 후 Yes, No를 return한다

string appendAndDelete(string s, string t, int k)
{
    int same = 0;
    
    for (int i = 0; i < s.size(); ++i)
    {
        if (s[i] == t[i])
            ++same;
        else
            break;
    }
    
    int sDiff = (s.length() - same);
    int tDiff = (t.length() - same);
    int diff = sDiff + tDiff;
    
    if (k >= diff && (k & 1) == (diff & 1))
        return "Yes";

    if (s.length() + t.length() <= k)
        return "Yes";
        
    return "No";
}

고려해야 할 상황이 굉장히 많은 문제고, 예외처리도 생각을 많이 해야 하는 문제다

 

첫번째로 s 문자열과 t 문자열이 시작부터 어디까지 같은지 체크해 same이라는 값으로 저장한다

 

이후 s의 길이에서 same을 뺀 값과 t의 길이에서 same을 뺀 값을 더해 s 문자열에서 t 문자열로 바꾸기 위해 몇번의 수정 작업을 해야하는지 구해 diff에 저장한다

 

만약 k의 값이 diff의 값과 같거나 크고, k와 diff가 짝수, 홀수 여부가 같다면 s문자열에서 k만큼 수정해서 t 문자열로 변경 할수 있으므로 Yes를 return 한다

 

k값이 diff보다 작다면 당연히 불가능하며, 또한 diff와 k의 홀 짝 여부가 맞지 않으면 자릿수를 동일하게 맞출 수 조차 없기 때문에 불가능하므로 두 조건을 만족해야한다

 

한가지 예외 사항이 있는데, 만약 s의 문자열 길이와 t의 문자열 길이를 합친 것보다 k의 크기가 크거나 같다면, 홀짝 여부와 관계 없이 s의 문자열 처음까지 싹 밀어버린 후 필요없는 횟수를 소모시켜버리고 t 문자열을 새로 써버리면 되기 때문에 이 경우에는 어떤 상황에 관계 없이 항상 Yes를 return 할 수 있다

 

만약 위 조건을 전부 만족하지 못한다면 변환이 불가능하므로 No를 return 한다