[HackerRank] Abbreviation

Abbreviation은 주어진 A 문자열에서 B문자열을 만들어 낼 수 있는지 판단하는 문제이다.

규칙은 다음과 같다.

• 규칙 1. A 문자열 중 소문자는 지울 수 있다.
• 규칙 2. A 문자열 중 소문자는 대문자로 변환 시킬 수 있다.

소문자는 없는 문자로 취급해도 되니, 순서에 맞게 B문자열이 나올 수만 있으면 정답이 될 것이다.

위의 규칙을 소스코드로 만들어 보면 다음과 같을 것이다.

    public static void abbreviation(String a, String b) {
    	if (b.length() == 0) { #3
            if (hasUpperCase(a) == false) {
                result = true;
            }
            return;
        }
        
        char aLetter = a.charAt(0);

        if (Character.isLowerCase(aLetter) == true) { #1
            abbreviation(a.substring(1), b);
        }
        if (Character.toUpperCase(aLetter) == b.charAt(0)) { #2
            abbreviation(a.substring(1), b.substring(1));
        }
        return;
    }
    
    static boolean hasUpperCase(String a) {
        for (int i = 0; i < a.length(); i++) {
            if (Character.isUpperCase(a.charAt(i))) {
                return true;
            }
        }
        return false;
    }

#1 if 문 : 소문자는 지울 수 있다.

#2 if문 : 소문자를 대문자로 바꿀 수 있다.

재귀를 통해 쉽게 구현을 할 수 있다. 항상 재귀는 탈출 조건을 가지고 있어야하는데 위의 문제 탈출 조건은 변환이 가능할 때와 그렇지 않을 때이다. #3에서 B 문자열이 존재하지 않을 때(#2에 의해서 지워진다.), A 문자열의 남은 문자열에 대문자가 있으면 답이 아닌 것으로 간주(#1의 조건 문에 의하여)한다.

예를 들어 A 문자열이 ABCdfgh이고 B 문자열이 ABC이면 ABC가 #2에 의해 맞아 떨어지고 A문자열이 dfgh가 남았을 경우 dfgh는 지울 수 있는 문자이므로 답이라고 본다.

 

하지만 위의 코드를 정답에 넣어보면 타임아웃이 나올 것이다. 

한가지 예시가 있다. dd라는 문자열이 A 문자열로 들어 왔을 때이다. 왼쪽으로 가면 규칙 1에 의해 소문자를 지우고 오른쪽으로 가면 규칙 2에 의해 대문자로 만든다. 만약 dd뒤에 더 많은 문자열이 있다면 리프 노드의 D는 중복이다. 문자열이 길어질 수록 이런 중복된 계산은 더 비효율적인 계산이 될 것이다. (마치 피보나치에서 중복 계산을 하는 것 처럼)

이러한 중복된 계산을 지우기 위해 미리 계산해 놓을 필요가 있다.

    public static void abbreviation(String a, String b) {
        if (b.length() == 0) {
            if (hasUpperCase(a) == false) {
                result = true;
            }
            return;
        }

        char aLetter = a.charAt(0);

        if (memo.containsKey(a) == true) {
            String memoB = memo.get(a);
            if (memoB.equals(b) == true) {
                return;
            }
        }
        memo.put(a, b);
        if (Character.isLowerCase(aLetter) == true) {
            abbreviation(a.substring(1), b);
        }
        if (Character.toUpperCase(aLetter) == b.charAt(0)) {
            abbreviation(a.substring(1), b.substring(1));
        }

        return;
    }

동적계획법을 활용하여 미리 계산된 값이 있는지 확인하는 코드 이다.

A 문자열이 ddA이고 B문자열이 DC라고 가정하면 경우의 수는 비교 가능한 경우의 수는 

["ddA", "DC"], ["dA", "DC"], ["A", "C"], ["DdA", "DC"], ["dA", "C"], ["A", "C"] 이고 ["A", "C"]가 2번 나오는 계산을 한다. 만약 A뒤의 문자열이 더 길어지면 어떨까? 문자열 A와 문자열 B의 키, 밸류 값으로 중복 계산을 막는 코드를 넣으므로 시간 복잡도는 훨씬 나아질 것으로 기대된다. 

public class Main {
    public static void abbreviation(String a, String b) {
        if (result == true) return;

        if (a.length() < b.length()) return;

        if (b.length() == 0) {
            if (hasUpperCase(a) == false) {
                result = true;
            }
            return;
        }

        char aLetter = a.charAt(0);

        if (memo.containsKey(a) == true) {
            String memoB = memo.get(a);
            if (memoB.equals(b) == true) {
                return;
            }
        }
        memo.put(a, b);
        if (Character.isLowerCase(aLetter) == true) {
            abbreviation(a.substring(1), b);
        }
        if (Character.toUpperCase(aLetter) == b.charAt(0)) {
            abbreviation(a.substring(1), b.substring(1));
        }

        return;
    }

    static boolean hasUpperCase(String a) {
        for (int i = 0; i < a.length(); i++) {
            if (Character.isUpperCase(a.charAt(i))) {
                return true;
            }
        }
        return false;
    }

    private static final Scanner scanner = new Scanner(System.in);
    private static boolean result = false;
    private static Map<String, String> memo = new HashMap<>();

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

        int q = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int qItr = 0; qItr < q; qItr++) {
            String a = scanner.nextLine();

            String b = scanner.nextLine();

            abbreviation(a, b);
            bufferedWriter.write(result == true ? "YES" : "NO");
            result = false;
            memo = new HashMap<>();
            bufferedWriter.newLine();
        }

        bufferedWriter.close();

        scanner.close();
    }
}