정렬] Find the Difference

LeetCode의 Easy 단계 문제를 풀어보았다. Find the Difference 문제다. 내 풀이[1][2]는 하단과 같았고, 개선사항[3]을 생각해보기 위해 실행 결과 남긴다.

 

class Solution {
    public char findTheDifference(String s, String t) {
        char alphabet = t.charAt(0); // initialization
        String rep;
        for (int i = 0, strLen = s.length(); i < strLen; i++) {
            alphabet = s.charAt(i);
            rep = remove(alphabet, t);
            
            if (rep.length() == 1) {
                alphabet = rep.charAt(0);
                break;
            } else {
                t = rep;
            }
        }
        return alphabet;
    }
    
    // return string replaced
    private String remove(char c, String t) {
        String cRegex = Character.toString(c);
        String result = t.replaceFirst(cRegex, "");
        // System.out.println(t + ":" + result);
        
        if (t.equals(result)) {
            return cRegex;
        }
        
        return result;
    }
}

 

 

 

_____

1. 두 문자열 s, t의 차이를 구하는 문제다. 문자열 t는 s보다 한 문자가 더 추가되었고, 추가 위치는 무작위다. 해서 생각한 풀이는 길이가 작은 문자열인 s를 반복하면서 t에 존재하면 제거 후 반환, 존재하지 않는다면 해당 문자를 반환하는 것이었다. 하지만 사실상 작은 문자열의 루프를 돌리므로, 마지막 하나가 남을 때까지 이중 반복을 돌게 되고(반복문 내 replaceFirst 메소드 호출) 시간 복잡도가 O(n²)이 되었다(확인 필요).

2. 한 글자 많은 문자열 t로 루프를 돌린다면 시간이 조금 감소하지 않을까 하였으나 다음 테스트 케이스에서 원하는 결과값이 나오지 않았다. 디버깅을 해도 잘... 조금 고민해봐야 할 듯 싶다.

/*
 * Input
 *  s: "ohkuhojcidclijdzajepmyykyzcuvrezmiunslwwouvpsnjikvlpcftvtcavccvwmryjumkusqghvakqdhglwczwmtiayjszzemuezcvoczdswzxblmvumykellolfajhdrsmubcinidyeqhoegyuipzhwwultuybryvvtmsjgzlhehatnxycxiijpxrxcfvfflbqmhggkflazwcwnxehznibgrjnwefiuhkfhfcaqaqyhqhkfzukljrfmvhuvviltoyleoxflljbuycntwsisyylpqumhseuusafakpcxbvfafvhbjfmwecapzxlvqcjvxxdqasemanjghpddviutehgwxslirhclzhctlvqqhqnbhaqnvepetqwtglmestiyjrwfoeurnntagvwwikqcnvyjahswzelcpnlvsjmmkoiqwzemivwyuumtkohtbblfjuarkvcfohdbwcvwylzbgxiyzmddjumneagbnjqizgeulbrmntttndckovkpfxqcxiyeavgouhmtcazcvjdgbauembtuhaphriynzymotwilkawjfliwznohwjnsubahqbcwgyzfbkxlksilmiumgmrvqyvjnnvlaoitnxgshplhhhxvxkajfgnzcvfzteqzqlgtpkgchfvleksbxvxynlaasdkdmuhtmqvzsxaecnbvivejbudwrmsxqxewokpfhuaukvxoizwnxlnorvnwdhgsxgxlrlwnhqlhfchsopwxviwbwqbkkyjmfxqfukyfxmbbq"
 *  t: "bubzjfvqkhtgfjmcrkiohqxqwjtuspmdgcnmyyzcyqmaufdhhecacstouacjlblazbiovvwuxygvuudqvqsvdlbjraiwexcfdkffvavkixgklrzeylatlnlhlzcpzsdhtgljaqstceqlthxrkhsurlxftvvhedjqiniuwgfdcnoeqsrmlspzohyjvnxrvlgykyvnsflvjcpihuiyqwrkxnekbcmkvlhaxlbsxbjnnmllolmmezdsdzjuhizhybhrtmcnwyhlocnhoazajnahezjnlutpygwociutuwuuxhtbaszhacbeekvnsosimpxdfzflrmzqffgemnzgnlukyuvhyfihwywxgezeshxoylfdfonjhbptkzxrnuuqcwsqsmgxwvwxlcbtamwvsjfkytvfqguluxkockezahgwuxpweliywlenbgnnpfzhbjhpzwqqimsgrarwfjbvtlvdmkhjkayfwgwmvhhpmuvnzyviugvpceovaaxeextwjzwvekhbirlwiqwfacogihlngatvpmxrvwwzuynxxfutkvhikmvevslaqqujevozsldwxeecfvhutqtqsvwtlljhuqcflkjgiotvcyvjibiovxvhrkmtuaekwwtyygoalgwcxcdiksjcbzbiyfnuuazijmbrhqhkjwhqnpnmiibfjqhfqdatgehnnivuexmovzmlizmuccihwkynbxyeccvbukmkfsajccpaaymmqqvaxhafxlmmcdipzopnwmllbynwmdsiebmb"
 * Output: "b"
 * Expected: "m"
 */
class Solution {
    public char findTheDifference(String s, String t) {
        char alphabet = t.charAt(0); // initialization
        String rep;
        for (int i = 0, strLen = t.length(); i < strLen; i++) {
            alphabet = t.charAt(i);
            rep = remove(alphabet, s);
            
            if (Character.toString(alphabet).equals(rep)) {
                System.out.println("**" + alphabet);
                break;
            } else {
                s = rep;
            }
        }
        return alphabet;
    }
    
    private String remove(char c, String s) {
        String cRegex = Character.toString(c);
        String result = s.replaceFirst(cRegex, "");
        // System.out.println(s + ":" + result);
        
        /*
         * abcd : abcde
         * abcd : abecd
         */
        if (s.equals(result)) {
            return cRegex;
        }
        
        return result;
    }
}

3. 기존 풀이가 실행 시간 및 메모리 둘 다 높게 나와서 뭐가 문제일까 하다가, 정렬을 하지 않고 비교했다는 것을 깨달았다. 해서 아래와 같이 정렬 후 비교해주었고, Primitive 타입 그대로 비교를 해주어서인지 메모리 사용[5]도 많이 줄어들었다.

class Solution {
    public char findTheDifference(String s, String t) {
        char[] ss = s.toCharArray();
        char[] ts = t.toCharArray();
		
        Arrays.sort(ss);
        Arrays.sort(ts);
		
        char result = ts[0];
        for (int i = 0, cLen = ts.length; i < cLen; i++) {
            if (i == cLen - 1) { // [4]
                result = ts[cLen - 1];
                break;
            }
            
            if (ss[i] != ts[i]) {
                result = ts[i];
                break;
            }
        }
        
        return result;
    }
}

4. 반복문 안에 조건문이 두 개가 있는데, 순서를 바꾸면 Runtime Error가 발생한다. 예를 들면 다음 테스트 케이스의 경우 때문이다.

"abcd"
"abcde"

5. 실행 시간 및 메모리 사용이 감소했음[6]을 확인할 수 있다.

6. 하지만 여전히 효율적이지 못한 풀이라는 것을 알 수 있다. 가장 성능이 좋은 타인의 풀이[8]를 하나씩 발췌한다.

 비교적 메모리 사용은 큰 차이 없는 듯 싶다.

/** 0ms submission */
class Solution {
    public char findTheDifference(String s, String t) {
  
        char[] ss = s.toCharArray();
        char[] ts = t.toCharArray();
        int count=0;
        for (int i = 0; i < ss.length; i++) {
            count -= ss[i];
            count += ts[i];
        }
        count += ts[ts.length - 1];

        return (char) (count);
    }
}

/** 1ms submission */
class Solution {
    public char findTheDifference(String s, String t) {
        char r = (char) 0;
        for (char c: s.toCharArray()) 
            r ^= c; // [7]
        for (char c: t.toCharArray())
            r ^= c;
        return r;
    }
}

/** 36700 KB submission */
class Solution {
    public char findTheDifference(String s, String t) {
        //doing this with bit manipulation
        int endRes = 0;
        for (int i = 0; i < s.length(); i++) {
            endRes = endRes ^ (int)s.charAt(i);
        }
        for (int i = 0; i < t.length(); i++) {
            endRes = endRes ^ (int)t.charAt(i);
        }
        return (char)endRes;
    }
}

7.

8. 같이 공부하는 동료가 이를