Grind 75: #7 Valid Anagram

0tak2 commented 5 days ago

Valid Anagram

0tak2 commented 5 days ago

처음에는 해시맵을 활용해서 구현했는데 생각보다 속도가 많이 느렸음
샘플 참고해서 해시테이블 대신 배열을 사용하여 다시 구현
알파벳은 그 자체로 순서를 가지기 떄문에, 해시함수 없이도 배열만으로 테이블처럼 활용 가능
이렇게 되면 해시함수를 거치지 않기 때문에 속도가 대폭 빨라지는 듯 함

public class Solution {
    // 2ms, 43.25MB
    public boolean isAnagram(String s, String t) {
        int[] memo = new int[26];

        for (char c : s.toCharArray()) {
            memo[c - 'a']++;
        }

        for (char c : t.toCharArray()) {
            if (memo[c - 'a'] >= 1) {
                memo[c - 'a']--;
            } else {
                return false;
            }
        }

        for (int count : memo) {
            if (count != 0) {
                return false;
            }
        }

        return true;
    }

    // 10ms, 44.86MB
    public boolean isAnagram_slow(String s, String t) {
        Map<Character, Integer> memo = new HashMap<>();

        for (char c : s.toCharArray()) {
            memo.compute(c, (k, v) -> {
                if (v == null) {
                    return 1;
                }

                return v + 1;
            });

            // more slow
            // 14ms, 45.02MB
            //
            // int prev = memo.getOrDefault(c, 0);
            // memo.put(c, prev + 1);
        }

        for (char c : t.toCharArray()) {
            int count = memo.getOrDefault(c, 0);

            if (count >= 1) {
                memo.put(c, count - 1);
            } else {
                return false;
            }
        }

        for (Map.Entry<Character, Integer> entry : memo.entrySet()) {
            if (entry.getValue() > 0) {
                return false;
            }
        }

        return true;
    }
}

sonic247897 commented 4 days ago

class Solution {
public:
    bool isAnagram(string s, string t) {
        // 5 * 10^4 길이 문자열이기 때문에 int형 배열로 '문자-발생 빈도'로 기록해도 overflow 발생하지 않음.
        // 알파벳 소문자 26자에 대한 발생 빈도가 일치하는지만 확인하면 된다.
        if (s.size() != t.size()) return false;

        vector<int> alpha_count(26, 0);

        for (int i = 0; i < s.size(); ++i) {
            alpha_count[s[i] - 'a']++;
        }
        for (int i = 0; i < t.size(); ++i) {
            alpha_count[t[i] - 'a']--;
            // s 문자열에 없는 문자를 사용하거나, 한 문자를 너무 많이 사용하면 false
            if (alpha_count[t[i] - 'a'] < 0) {
                return false;
            }
        }

        return true;
    }
};

sonic247897 commented 4 days ago

오 해시맵도 삽입, 탐색에 O(1) 걸려서 배열과 비슷할 줄 알았는데 시간이 오래걸리네요. 좀 더 찾아보니까 해시 충돌이 발생할 경우에는 O(n)이 걸릴 수도 있다고 하니 가급적 배열을 사용하는 것이 좋군요~ 배웠네요

hotpineapple commented 2 days ago

아이디어: 문자를 인덱스로 가지는 배열에 문자 개수를 카운트 하여 이용

구현

class Solution {
public boolean isAnagram(String s, String t) {
    int[] cnt1 = new int[26];
    int[] cnt2 = new int[26];
    for (int i=0;i<s.length();i++){
        cnt1[s.charAt(i)-'a']++;
    }
    for (int i=0;i<t.length();i++){
        cnt2[t.charAt(i)-'a']++;
    }

    for (int i=0;i<26;i++) {
        if(cnt1[i]!=cnt2[i]) return false;
    }
    return true;
}
}

follow up : 문자열이 unicode 를 포함한다면?
- 해시맵을 사용할 수 있을 것 같다.

0tak2 commented 2 days ago

@sonic247897

코멘트 달아주신 덕분에 정말로 "해시함수를 거치지 않기 때문에" 빨라지는게 맞나? 의문이 들어서 고민을 좀 해봤습니다...

1. HashMap의 해시함수

HashMap::hash는 Object의 hashCode를 실행해 반환받은 값을 비트연산한 값을 취함 -> 단순히 해시충돌 가능성을 줄이기 위한 간단한 비트 뻥튀기
자바에서 모든 참조타입(클래스)은 Object를 상속하며, 대부분의 클래스는 각 인스턴스의 동등성을 비교하기 위해 hashCode와 equals 메서드를 오버라이드하도록 권장됨
- 동등하다(equivalent): Person#102201 (name="홍길동", birth="1443-1-1") 및 Person#354363 (name="홍길동", birth="1443-1-1")과 같이, 실제 메모리 주소의 동일 여부와 상관 없이 구성하는 프로퍼티 값이 같아 도메인 내에서 동등하게 취급되는 경우 (참고: Object::equals)
- equals 메서드로 비교했을 때 동등한 두 인스턴스는 hashCode의 반환값이 동일해야함 (ref: [Object::hashCode](https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/lang/Object.html#hashCode()))
String의 경우 문자열을 구성하는 각 글자를 순회하면서 누적하는 방식으로 hashCode를 계산하도록 오버라이드됨
- 라틴 기준이지만, 유니코드도 비슷하게 구현됨
- 수행 시간은 글자 수에 비례 (O(N))
- String이 한 글자 영어 알바벳인 경우, h가 0이고 루프를 한 번 돌기 때문에 아스키코드와 동일 (ex> "A".hashCode() == 65 // true)

2. 해시합수 실행 비용

이 문제에서 해시테이블을 사용하게 되는 경우, 한 글자의 영어 알파벳을 키로 사용하게 되므로, 연산 비용이 그다지 크지 않을 것 같습니다.

3. 해시 콜리전 가능성

해시 콜리전이 발생하면, 탐색시 시간 복잡도가 O(N)으로 증가하지만, 이 문제에서는 키로 한 글자의 영어 알파벳을 사용할 뿐이기 때문에 해시 콜리전은 아마도 발생하지 않습니다 test

4. 벤치마킹

그럼에도 다음과 같이 HashMap에 대한 입출력과 배열에 대한 입출력 성능을 비교해보면, test

    @Test
    void benchHashMap() {
        Map<String, Integer> map = new HashMap<>();
        Integer[] arr = new Integer[26];

        // 해시맵 입출력 - 29ms
        Long step1Start = System.currentTimeMillis();
        for (int i=0; i<100000; i++) {
            for (int j=0; j<26; j++) {
                map.compute(chars[j], (key, value) -> value == null ? 0 : value + 1);
            }
        }
        Long step1End = System.currentTimeMillis();

        // 단순 배열 입출력 - 10ms
        Long step2Start = System.currentTimeMillis();
        for (int i=0; i<100000; i++) {
            for (int j=0; j<26; j++) {
                if (arr[j] == null) {
                    arr[j] = 0;
                } else {
                    arr[j]++;
                }
            }
        }
        Long step2End = System.currentTimeMillis();

        System.out.println(step1End - step1Start + "ms");
        System.out.println(step2End - step2Start + "ms");
    }

100000*26건에 대해서 29ms와 10ms로 약 3배 정도 차이가 나게 됩니다.

해시맵을 사용하게 되는 경우 해시함수가 비용이 크기 때문에, 또는 해시 콜리전이 발생했기 때문에 그런 것 같지는 않고...

그래도 콜스택이 늘어나기는 한다는 점 -- 입출력할 때마다 HashMap 메서드를 호출하게 되고 한 번의 호출에 수번~수십번의 함수가 호출됨
배열의 메모리 구조상 단순함

이런 이유들이 아닐까...? 싶습니다

의견 있으시면 공유해주시면 좋을 것 같아요

sonic247897 / 2024_algorithm_study