[알고리즘] 빈도수 세기 패턴(Frequency Counters -java)

[알고리즘 기초] 빈도수 세기 패턴(Frequency Counters -java)

JavaScript (JS) Algorithms and Data Structures Masterclass | Udemy
해당 포스팅은 JavaScript 알고리즘 & 자료구조 마스터클래스강의를 참고하여 작성했습니다.

알고리즘에 있어 자주 사용되는 문제 해결 패턴에 대해서 소개하겠습니다.
여기서 소개하는 패턴은 코드는 알고리즘 문제를 해결하는데 있어 일반적인 접근법이 될수 있지만, 모든 경우를 포괄하지 않습니다.
또한, 해당 패턴이름은 정식 명칭도 아닙니다.!

음.. 비유를 하자면, 수학문제를 풀때 우리가 구구단을 외운 것 처럼
패턴 코드를 숙지하고 암기하고 있으면 알고리즘 문제를 해결하는데 많은 도움을 줄 것입니다.🤗

 

빈도수 세기 패턴(Frequency Counters)

첫 번째 배열에 값의 제곱값이 두 번째 배열에 포함되어 있으면 참을 반환하는 함수를 작성하세요.
첫 번째 배열의 값의 제곱값이 두 번째 배열에 중복으로 존재하면 거짓 입니다.
두 번째 배열의 순서는 상관 없습니다.

예시)
A[1, 2, 3], B[1, 4, 9] -> true
A[1, 2, 3], B[4, 9, 1] -> true (순서는 상관 없습니다.)
A[1, 2, 3], B[1, 9] -> false (4가 없어서 거짓)
A[1, 2, 1], B[1, 1, 4] -> true
A[1, 2, 1], B[4, 1, 4] -> false (빈도가 다르기 때문에 거짓, 4 대신 1이 있어야 참)

먼저 간단하게 구현해보겠습니다.

simpleFrequencyCounters

// O(N^2)
boolean simpleFrequencyCounters(List<Double> arr1, List<Double> arr2) {
    // arr1과 arr2의 크기가 다르면 거짓
    if(arr1.size() != arr2.size()) {
        return false;
    }
    for(int i = 0; i < arr1.size(); i++) { // O(N)
        // indexOf(): 처음 발견되는 인덱스 반환, 찾지 못하면 -1 반환
        int value = arr2.indexOf(Math.pow(arr1.get(i), 2));
        // 찾지 못하면 false
        if(value == -1) {
            return false;
        }
        // 찾으면 해당 값 삭제
        arr2.remove(value); // O(N)
    }
    return true;
}

가능한 중첩 loop를 사용하는 것은 좋지 않습니다.

이제 빈도수 카운터 패턴(Frequency Counters)을 적용해보겠습니다.

frequencyCounters

HashMap을 이용하여 O(N) 알고리즘으로 구현할 수 있습니다.
여기서 중요한 포인트는 key에는 배열의 값을, value에는 배열 값의 갯수를 넣어 주어 문제를 해결하는 것 입니다.

• frequencyCounters
  • key : 배열 값
  • value : 배열 값의 갯수

boolean frequencyCounters(List<Double> arr1, List<Double> arr2) {
    // arr1과 arr2의 크기가 다르면 거짓
    if(arr1.size() != arr2.size()) {
        return false;
    }

    // key: 배열 값, value: 갯수
    Map<Double, Integer> frequencyCounters1 = new HashMap<>();
    Map<Double, Integer> frequencyCounters2 = new HashMap<>();

    //O(N)
    for(Double num : arr1) {
        if(frequencyCounters1.containsKey(num)) {
            Integer count = frequencyCounters1.get(num);
            frequencyCounters1.put(num, ++count);
        } else {
            frequencyCounters1.put(num, 1);
        }
    }
    //O(N)
    for(Double num : arr2) {
        if(frequencyCounters2.containsKey(num)) {
            Integer count = frequencyCounters2.get(num);
            frequencyCounters2.put(num, ++count);
        } else {
            frequencyCounters2.put(num, 1);
        }
    }

    /**
     * arr1[1, 2, 3], arr2[4, 1, 4] 일때
     * frequencyCounters1[1:1, 2:1, 3:1]
     * frequencyCounters2[4:2, 1:1]
     */
    //O(N)
    for (Map.Entry<Double, Integer> doubleIntegerEntry : frequencyCounters1.entrySet()) {
        Double key = doubleIntegerEntry.getKey();
        double powKey = Math.pow(key, 2);
        //O(1)
        if(!frequencyCounters2.containsKey(powKey)) {
            return false;
        }
        //O(1)
        if(!frequencyCounters2.get(powKey).equals(frequencyCounters1.get(key))) {
            return false;
        }
    }

    return true;
}

Big-O의 복잡성 측면에서 simpleFrequencyCounters 보다 frequencyCounters가 더 낫다는 것을 이해할수 있어야 합니다.

TEST

@Slf4j
public class FrequencyCounters {

    @Test
    void test() {
        List<Double> arr1 = new ArrayList<>() {{
            add(1d);
            add(2d);
            add(3d);
            add(5d);
            add(5d);
        }};
        List<Double> arr2 = new ArrayList<>() {{
            add(9d);
            add(1d);
            add(25d);
            add(4d);
            add(25d);
        }};
//        boolean result1 = simpleFrequencyCounters(arr1, arr2);
//        log.info("result1={}", result1);
        boolean result2 = frequencyCounters(arr1, arr2);
        log.info("result2={}", result2);
    }
}

문자 빈도수 확인(아나그램)

앞에서 배운 Frequency Counters를 활용하여
2개의 문자열의 문자 빈도수를 확인하는 알고리즘을 작성해보세요!
사용된 문자의 수가 같으면 참, 다르면 거짓 입니다.(대소문자는 구분 없이 진행합니다.)

예시)
Aaa, zza -> false
anagram, nagaram -> true
minkai, kaimiN -> true

Anagram

@Slf4j
public class Anagram {

    @Test
    void test() {
        Assertions.assertThat(validAnagram("", "")).isTrue();
        Assertions.assertThat(validAnagram("aaz", "zza")).isFalse();
        Assertions.assertThat(validAnagram("anagram", "nagaram")).isTrue();
        Assertions.assertThat(validAnagram("rat", "car")).isFalse();
        Assertions.assertThat(validAnagram("awesome", "awesom")).isFalse();
        Assertions.assertThat(validAnagram("amanaplanacanalpanama", "acanalmanplanpamana")).isFalse();
        Assertions.assertThat(validAnagram("qwerty", "qeywrt")).isTrue();
        Assertions.assertThat(validAnagram("texttwisttime", "timetwisttext")).isTrue();
        Assertions.assertThat(validAnagram("minkai", "kaimin")).isTrue();
    }

    boolean validAnagram(String arrStr1, String arrStr2) {
        // 소문자로 변경하고 char 배열로 변환
        char[] chars1 = arrStr1.toLowerCase().toCharArray();
        char[] chars2 = arrStr2.toLowerCase().toCharArray();

        // 배열의 길이가 다르면
        if(chars1.length != chars2.length) {
            return false;
        }

        // key: 문자, value: 문자 갯수 로 표현
        Map<Character, Integer> strCounter1 = new HashMap<>();
        Map<Character, Integer> strCounter2 = new HashMap<>();

        for(Character ch : chars1) {
            if(strCounter1.containsKey(ch)) {
                Integer counter = strCounter1.get(ch);
                strCounter1.put(ch, ++counter);
            } else {
                strCounter1.put(ch, 1);
            }
        }

        for(Character ch : chars2) {
            if(strCounter2.containsKey(ch)) {
                Integer counter = strCounter2.get(ch);
                strCounter2.put(ch, ++counter);
            } else {
                strCounter2.put(ch, 1);
            }
        }

        for(Map.Entry<Character, Integer> entry : strCounter1.entrySet()) {
            Character key = entry.getKey();
            Integer value = entry.getValue();
            // strCounter2에 strCounter1의 key(문자)가 없으면
            if(!strCounter2.containsKey(key)) {
                return false;
            }
            // strCounter2와 strCounter1의 value가 다르면
            if(!strCounter2.get(key).equals(value)) {
                return false;
            }
        }

        return true;
    }
}

정리

• HashMap을 이용하여 key와 value로 분류하는 생각을 한다.
  • key는 분류 대상
  • value는 분류 대상의 출현 빈도수