[Algorithm] 최빈값 찾기

문제 , 입력, 출력

Q. 다음과 같은 문자열을 입력받았을 때, 어떤 알파벳이 가장 많이 포함되어 있는지 반환하시오. (단 최빈값을 가진 알파벳이 여러개일 경우 알파벳 순서가 가장 앞에 위치한 알파벳을 출력하시오) 라는 문제인데, 예를 들어 입력이 aaaabbbccd 라면, a 가 출력이 되면 된다.

내가 처음 풀었을 때는 다음과 같이 해결 했다.(편의상 콘솔 입력은 생략)

SolutionV0

 static String findMaxOccurredAlphabetV0(String string) {
        // 문자열을 먼저 쪼개 봅시다
        String[] arr = string.split("");

        // 알파벳을 카운팅할 배열도 만듭시다
        // a = 0 , b = 1 , c = 2 ... z = 25
        int[] alpha = new int[26];

        // 공백도 제거 해야겠지요? -> 빌더 타입을 씁시다
        StringBuilder sb = new StringBuilder();

        for (String s : arr) {
            if (!s.equals(" ")) {
                sb.append(s);
            }
        }

        char[] temp = sb.toString().toCharArray();

        // 이제 아스키 코드로 다시 풀어볼게요 -> 97 빼기
        for (char c : temp) {
            int index = c - 97;
            alpha[index]++;
        }

        // 그럼 이제 순회 하면서 가장 많이 있는 알파벳을 찾아봐요

        int max = 0;
        int maxIndex = 0;
        for (int i = 0; i < alpha.length; i++) {
            if (alpha[i] > max) {
                max = alpha[i];
                maxIndex = i;
            }
        }

        char result = (char) (maxIndex + 97);
        return String.valueOf(result);
    }

쉽게 한줄씩 로직을 주석으로 적고 구현하는 방식으로 작성했다.

즉, 해결 순서는 다음과 같았는데

1. 입력 문자 쪼개서 배열로 생성 + 알파벳에 매핑 시킬 26크기의 배열도 생성

2. 입력 문자 배열의 공백문자를 제거하기 위한 Builder 패턴 사용 후 다시 배열로 생성

3. char 타입 배열로 변환 후 최대 값과 최대 인덱스 값을 갱신하며 반복문 실행

4. 최종 아스키 코드로 출력하기 위해 +97 매핑 후 리턴

위와 같은 방법으로 일단 돌아가게 만들어 놓고, 다음과 같이 리팩토링 했다.

 

SolutionV1

static String findMaxOccurredAlphabetV1(String string) {
        // 알파벳 매핑 배열
        int[] alphabetOccurrence = new int[26];

        char[] array = string.toCharArray();
        for (char c : array) {
            if (Character.isAlphabetic(c)) {
                int index = c - 97;
                alphabetOccurrence[index]++;
            }
        }

        int maxOccurrence = 0;
        int maxAlphabetIndex = 0;

        for (int i = 0; i < alphabetOccurrence.length; i++) {
            if (alphabetOccurrence[i] > maxOccurrence) {
                maxOccurrence = alphabetOccurrence[i];
                maxAlphabetIndex = i;
            }
        }

        return String.valueOf((char) (maxAlphabetIndex + 97));
    }

V1은 V0과 비교하여 다음과 같은 차이점이 존재한다

1. 배열을 쪼개고, Bulider타입으로 변환하고 다시 char 타입 배열로 변환 하는 대신에 Character.isAlphabetic 메서드로 해당 문자가 알파벳이면 해당 문자를 아스키코드화 (배열 인덱스화) 시켜서 해당 배열의 값을 증가

2. 이후 로직은 동일

 

불필요한 반복문 사용 및 공간 복잡도가 많이 줄은 것을 확인할 수 있다

그리고 결과는 동일하다 !