GFG Count the Substrings 자바 문제 풀이

문제

Problem_Link

문제해결방법

• 조건: 대문자와 소문자의 개수가 같은 substring
• 특정 substring의 시작점과 끝점의 대소문자 차이가 같다면, 그 substring은 조건에 맞는 substring 이라 볼수 있다.

예제: “AbaBBa”

• 위 예제의 substring의 총 개수는 21개 이며, 조건에 맞는 substring은 7개이다.
• 대소문자 차이를 구하기 위해 대문자이면 +1을, 소문자이면 -1을 사용한다.
• 시작점은 대소문자 차이가 없으므로 0이다.

index	없음	0	1	2	3	4	5
element	시작점	A	b	a	B	B	a
대소문자 차이	0	1	0	-1	0	1	0

같은 대소문자 차이를 가지고 있는 사이의 substring은 조건에 맞는 substring이다.

substring	index	대소문자 차이
Ab	없음~2	0
aB	2~4	0
Ba	4~6	0
AbaB	없음~4	0
baBB	1~5	0
aBBa	2~6	0
AbaBBa	1~5	1

*첫번째 인덱스는 포함하지않고, 마지막 인덱스는 포함한다. 이는 시작점이 0이고 인덱스가 없기 때문이다.

시간복잡도: O(n), 공간복잡도: O(n)

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

public class BalancedSubstring {
    public static void main(String[] args) {
        String S = "AbaBBa";
        System.out.println(countSubstring(S));
    }

    public static int countSubstring(String S) {
        int n = S.length();
        int count = 0;
        int diff = 0;
        Map<Integer, Integer> diffMap = new HashMap<>();

        // 대소문자 차이 0을 가진 diffMap 초기화
        diffMap.put(0, 1);

        for (int i = 0; i < n; i++) {
            char c = S.charAt(i);

            // 대문자와 소문자의 차이를 업데이트
            if (Character.isUpperCase(c)) {
                diff++;
            } else if (Character.isLowerCase(c)) {
                diff--;
            }

            // 이전에 발견된 차이에 기반하여 count 증가
		        // 현재 차이가 이전에 발견되었다면, 대문자와 소문자의 수가 같은 서브스트링이 있다는 것을 의미합니다.
		        count += diffMap.getOrDefault(diff, 0);

		        // 현재 차이와 그 횟수를 업데이트하여 차이 맵을 업데이트
		        diffMap.put(diff, diffMap.getOrDefault(diff, 0) + 1);
        }

        return count;
    }
}

설명

1. 먼저, diffMap이라는 HashMap을 초기화합니다. 이 맵은 대문자와 소문자의 개수 차이를 저장하는 데 사용됩니다. 초기에 차이가 0이므로, 맵에 (0, 1)을 넣어줍니다.
2. 입력 문자열 S를 순회하기 위해 for 반복문을 사용합니다. 반복문은 인덱스 0부터 문자열의 길이보다 작을 때까지 실행됩니다.
3. 각 인덱스에서의 문자 c를 가져와서 대문자인지 소문자인지 확인합니다. 대문자인 경우, 차이 diff를 1 증가시키고, 소문자인 경우 1 감소시킵니다.
4. 현재 차이 diff가 이전에 발견된 경우, 대문자와 소문자의 개수가 동일한 서브스트링이 있다는 것을 의미합니다. 따라서, 이전에 발견된 차이가 동일한 경우의 수를 count에 더합니다. 만약 차이가 없었다면, getOrDefault 메소드를 사용해 0을 반환합니다.
5. 현재 차이 diff를 사용하여 diffMap을 업데이트합니다. diff가 이미 존재한다면, 해당 값에 1을 더해주고, 존재하지 않는 경우 새로운 차이로 추가합니다.
6. for 반복문이 끝난 후, 카운트 count에 저장된 값을 반환합니다. 이 값은 대문자와 소문자의 개수가 동일한 서브스트링의 개수입니다.