[Leetcode]1781. Sum of Beauty of All Substrings

문제 요약

• 알고리즘 분류:  구현, 문자열, 해쉬
•  
• 난이도: Medium
• 문제내용:
  • 문자열의 "아름다움(beauty)"은 가장 많이 나타나는 문자와 가장 적게 나타나는 문자의 빈도 차이로 정의됩니다.
    • 예를 들어, 문자열 "abaacc"의 아름다움은 3−1=23 - 1 = 23−1=2입니다.
  • 문자열 sss가 주어졌을 때, sss의 모든 부분 문자열(substring)의 아름다움의 합을 반환하세요
• 사이트 주소:https://leetcode.com/problems/sum-of-beauty-of-all-substrings/description/ 

문제풀이

이번 문제는 주어진 문자열에서 모든 부분 문자열을 추출하여 각 부분 문자열의 "아름다움"을 계산하고 이를 합산하는 문제입니다. 문제를 해결하기 위한 과정은 다음과 같습니다.

 

1. 문자열의 시작 인덱스를 기준으로 0부터 끝까지 첫 번째 for문을 실행합니다.
2. 각 시작 인덱스에서 끝까지 두 번째 for문을 실행하며 부분 문자열을 생성합니다.
3. 생성된 부분 문자열에서 각 문자의 빈도를 계산하고, 최대 빈도와 최소 빈도의 차이를 구해 결과값에 누적합니다.

자세한 것은 아래 코드를 참고하면 자세한 구현 방법을 확인할 수 있습니다.

이중 for문을 사용하기 때문에 시간 복잡도는 O(N^2)에 해당합니다.

 

Code

Python

class Solution:
    def beautySum(self, s: str) -> int:

        result = 0 # 결과값을 저장할 변수
        size = len(s) # 문자열의 길이를 저장

        # 부분 문자열의 시작 인덱스를 지정하는 루프
        for i in range(size):

            info = dict({}) # 각 문자의 빈도수를 저장하기 위한 딕셔너리
            # 부분 문자열의 끝 인덱스를 지정하는 루프
            for j in range(i, size):
                # 현재 문자의 빈도수를 딕셔너리에 추가하거나 갱신
                info[s[j]] = info.get(s[j], 0) + 1
                # 빈도수 딕셔너리에서 최대값과 최소값의 차이를 결과값에 더함
                result += max(info.values()) - min(info.values())

        # 모든 부분 문자열의 아름다움의 합 반환
        return result

 

Java

 파이썬에서는 딕셔너리(Dictionary)를 사용해 쉽게 처리할 수 있지만, 자바에서는 배열을 활용한 방식을 보여주려 합니다.
그 이유는 파이썬은 내장 함수로 딕셔너리를 제공하지만, 자바에서 Map을 사용하려면 추가로 import가 필요합니다. 따라서 불필요한 import를 피하기 위해 배열을 사용하는 방식이 더 효율적일 수 있습니다.

또한, 자바에서는 문자형(Character)이 ASCII 코드 값으로 변환되기 때문에 문자 - 'a'와 같은 연산을 통해 문자 'a'부터 'z'를 0부터 25까지의 인덱스로 저장할 수 있습니다.

class Solution {
    public int beautySum(String s) {

        int result = 0; // 결과값을 저장할 변수

        int size = s.length(); // 문자열의 길이

        // 부분 문자열의 시작 위치를 지정하는 루프
        for (int start = 0; start < size; start++) {
            // 각 문자(a~z)의 빈도수를 저장할 배열
            int[] info = new int[26];

            // 부분 문자열의 끝 위치를 지정하는 루프
            for (int end = start; end < size; end++) {
                // 현재 문자의 빈도수를 증가
                ++info[s.charAt(end) - 'a'];

                // 빈도수의 최대값과 최소값을 저장할 변수 초기화
                int maxValue = 0;
                int minVale = 500;

                // 현재까지의 빈도수 배열을 탐색
                for (int cnt : info) {
                    if (cnt > 0) { // 빈도수가 0이 아닌 경우만 계산
                        maxValue = Math.max(maxValue, cnt); // 최대 빈도수 갱신
                        minVale = Math.min(minVale, cnt);  // 최소 빈도수 갱신
                    }
                }

                // 최대값과 최소값의 차이를 결과에 추가
                result += Math.max(maxValue - minVale, 0);
            }
        }

        // 모든 부분 문자열의 아름다움의 합 반환
        return result;
        
    }
}