2025 답/해설 없는 최신 코테 풀이 도전 메모기록 - 3

코드 풀이 시각화:)

 

문제 설명

두 개의 랜덤 문자열 s, t가 주어진다. 이때, 한 문자열 또는 양쪽 문자열에서 총 최대 2글자를 삭제하여 두 문자열이 완전히 동일해질 수 있는지 판단하는 문제이다.

• 삭제 연산만 허용하며, 삽입이나 교체는 불가능.
• 삭제 횟수의 합이 2를 넘으면 안 된다.

s = "abcde"
t = "ade"
# "abcde"에서 'b','c'를 삭제하면 "ade"가 되어 같아지므로 True.

해결 아이디어

1. 길이 차이 배제: |len(s) - len(t)| > 2라면 최대 2회 삭제로 같아질 수 없으므로 곧바로 False.
2. 투 포인터 + 재귀 백트래킹:
   • 두 문자열을 각각 포인터 i, j로 순회.
   • 남은 삭제 예산 rem을 함께 관리.
   • 문자가 같으면 (i+1, j+1, rem)으로 진행.
   • 다르면 두 가지 선택지:
     1. s[i] 삭제 → (i+1, j, rem-1)
     2. t[j] 삭제 → (i, j+1, rem-1)
   • rem < 0이 되면 더 이상 탐색하지 않고 False.
   • 한쪽만 끝에 도달했을 때 남은 문자 수(len(s)-i + len(t)-j)가 rem 이하이면 True.

시간 복잡도

최대 rem=2번만 분기 → 경로 수는 2^2 = 4개이다.
각 경로는 두 포인터가 문자열 끝까지 한 번씩 순회하므로, O(n).
따라서 O(4·n) = O(n) 으로 백트래킹이지만 충분히 빠르다.

 

Python

def can_match(s, t, k=2):
    # 길이 차이 배제
    if abs(len(s) - len(t)) > k:
        return False

    def dfs(i, j, rem):
        if rem < 0:
            return False
        # 두 문자열 모두 끝에 도달
        if i == len(s) and j == len(t):
            return True

        # 한쪽만 남았을때 모두 삭제로 소화 가능한지
        if i == len(s) or j == len(t):
            return (len(s) - i + len(t) - j) <= rem

        if s[i] == t[j]:
            return dfs(i + 1, j + 1, rem)
        # 불일치 시 두가지 삭제 분기
        return dfs(i + 1, j, rem - 1) or dfs(i, j + 1, rem - 1)

    return dfs(0, 0, k)

 

Java

public class N사_복원 {

    public static void main(String[] args) {
        String s = "abcde";
        String t = "ade";
        System.out.println(canMatch(s, t, 2)); // true
    }

    private static boolean canMatch(String s, String t, int k) {
        // 길이 차이 배제
        if (Math.abs(s.length() - t.length()) > k) return false;
        return dfs(s, t, 0, 0, k);
    }

    private static boolean dfs(String s, String t, int i, int j, int rem) {
        if (rem < 0) return false;
        // 종료조건
        // 두 문자열 모두 끝에도달
        if (i == s.length() && j == t.length()) return true;
        // 한쪽만 남았을 때 삭제로 처리 가능 여부
        if (i == s.length() || j == t.length()) {
            return (s.length() - i + t.length() - j) <= rem;
        }

        if (s.charAt(i) == t.charAt(j)) {
            return dfs(s, t, i + 1, j + 1, rem);
        }
        // 불일치 시 s 또는 t에서 문자 삭제
        return dfs(s, t, i + 1, j, rem - 1) || dfs(s, t, i, j + 1, rem - 1);
    }
}