Codewars 6kyu - Counting Duplicates 문제 풀이

문제 설명

Count the number of Duplicates

Write a function that will return the count of distinct case-insensitive alphabetic characters and numeric digits that occur more than once in the input string. The input string can be assumed to contain only alphabets (both uppercase and lowercase) and numeric digits.

Example

"abcde" -> 0 # no characters repeats more than once
"aabbcde" -> 2 # 'a' and 'b'
"aabBcde" -> 2 # 'a' occurs twice and 'b' twice (`b` and `B`)
"indivisibility" -> 1 # 'i' occurs six times
"Indivisibilities" -> 2 # 'i' occurs seven times and 's' occurs twice
"aA11" -> 2 # 'a' and '1'
"ABBA" -> 2 # 'A' and 'B' each occur twice

 

간단 설명

- 주어진 문자열에서 중복이 있는 문자의 갯수를 구하라

  - 예 : "abbccc"가 있다면 b와 c가 각각 2개와 3개로 중복이 있으므로 총 2개의 중복이 있는 문자(b와 c)가 존재 => 2 반환

- 대소문자는 구분하지 않는다.

- 입력으로 들어오는 문자열은 알파벳과 숫자만 포함

 

문제의 자세한 내용은 해당 링크를 통해 확인 : 문제 링크

 

풀이 코드

첫 번째 해결 코드

import java.util.Map;
import java.util.HashMap;

public class CountingDuplicates {
  public static int duplicateCount(String text) {
    Map<Character, Integer> countMap = new HashMap<>();
    
    text = text.toLowerCase();
    for (char key : text.toCharArray()) {
      countMap.put(key, countMap.getOrDefault(key, 0) + 1);
    }
    
    return (int) countMap.values().stream()
      .filter(e -> e > 1)
      .count();
  }
}

 

두 번째 해결 코드

public class CountingDuplicates {
    public static int duplicateCount(String text) {
        int answer = 0, length = 0;

        text = text.toLowerCase();
        while ((length = text.length()) > 0) {
            char c = text.charAt(0);
            text = text.replace(Character.toString(c), "");
            if (length - 1 != text.length()) {
                answer += 1;
            }
        }
        return answer;
    }
}

 

문제 해결 전략

이라 쓰고 문제를 보고서 어떻게 풀면 될까?에 대한 생각을 정리한 항목

들어가기 앞서 첫 번째 코드도 그렇지만 두 번째 코드도 실제 로직 진입 전 모든 문자를 소문자로 치환 후 동작하도록 하였습니다. 문제에서 대소문자 구분을 하지 않는다고 했기 때문입니다.

일단 첫 번째 코드의 경우 문제가 중복인 문자를 찾는 것이기 때문에 간단하게 String을 char[]로 변환 후 이를 순회하면서 Map의 Key 값으로 사용해 카운트 후 Value가 2 이상인 값을 카운트해서 반환하도록 구현을 했습니다.

간단한 방법이기 때문에 무언가 더 설명할 내용이 없네요. 해당 내용은 코드도 짧기에 쉽게 읽히기도 하고요.

두 번째 코드의 경우는 해결 후 다른 사람의 풀이를 보는데 가장 많은 투표를 받은 코드에서 영감을 받아 구현을 한 코드입니다.

굳이 구현을 해 본 이유는 가장 많은 투표를 받은 풀이 코드의 효율이 그다지 좋아 보이지 않는 코드였고, 그렇기 때문에 '이 정도로 투표를 받을 코드가 아닌 것 같은데..?'라는 생각이 들었습니다. 실제로 해당 코드의 댓글에도 이렇게 많은 투표를 받을 코드는 아니지 않느냐는 의견이 여럿 있었습니다.

아무튼 해당 코드는 replace를 사용하여 해결을 했었는데 'replace를 사용한 방식에서 조금 더 다음을 수 있지 않을까?'라는 생각으로 구현을 해보게 된 코드입니다. 문자열의 길이를 측정 후 replace로 문자열의 첫 글자를 제거한 문자열의 길이가 이전 길이와 2 이상 차이가 나는 경우에 카운트를 증가시키고, 이를 반복하여 결과를 도출합니다.

해당 코드는 중복되는 단어가 많을수록 반복이 줄어들어 효율이 좀 더 좋지 않을까 싶지만.. replace와 toString을 반복적으로 사용하기 때문에 String 객체를 계속 생성한다는 단점이 있긴 합니다. 따라서 중복 문자가 많은 문자열에 대해선 효율이 좋을 것 같지만 문자 중복이 없는 긴 문자열의 경우 첫 번째 코드 대비 시간 복잡도나 공간 복잡도 효율이 산으로 갈 것 같네요.