85일 (1525. Number of Good Ways to Split a String) String

You are given a string s.

A split is called good if you can split s into two non-empty strings sleft and sright where their concatenation is equal to s (i.e., sleft + sright = s) and the number of distinct letters in sleft and sright is the same.

Return the number of good splits you can make in s.

 

Example 1:

Input: s = "aacaba"
Output: 2
Explanation: There are 5 ways to split "aacaba" and 2 of them are good. 
("a", "acaba") Left string and right string contains 1 and 3 different letters respectively.
("aa", "caba") Left string and right string contains 1 and 3 different letters respectively.
("aac", "aba") Left string and right string contains 2 and 2 different letters respectively (good split).
("aaca", "ba") Left string and right string contains 2 and 2 different letters respectively (good split).
("aacab", "a") Left string and right string contains 3 and 1 different letters respectively.

Example 2:

Input: s = "abcd"
Output: 1
Explanation: Split the string as follows ("ab", "cd").

 

Constraints:

• 1 <= s.length <= 10^5
• s consists of only lowercase English letters.

 

- 접근방법

 

1번째 방법 : exmaple1의 right를 map자료구조로, left를 set자료구조로 구현하였다.

(코드를 다듬어도 느려서 폐기)

 

 

2번째 방법 : 알파벳은 26글자이고, 'a' - 97 = 0, 'z' - 97 = 25이다. 그러므로

26개의 공간의 정수형 1차원배열을 활용하여 자료구조 map과 set을 대신하였다.

 

1.  만약 arr[3] = 5이라면 'd'가 5번 카운트된 것이고,  arr[25] = 1 이라면 'z'가 1번 카운트되었다는 뜻으로 사용하였다.

이를 이용하여 arr[i] > 0 이라면 answer++를 하여 모든 고유원소의 개수를 구하였다.

 

2. 시작되는 left에 카운트 된 원소가 arr[3] = 5라면 arr[3] = -4로 변환한다.

left에 카운트 된 수를 표시하기 위해 양수에서 음수로 바꾼 것뿐이다.

 

3. arr[3] = 5 였기 때문에 문자열이 끝날때까지 'd'가 앞으로 4번 더 나올 것이기 때문에 5에서 -4가 된 것이다.

arr[3] 은 결국 0이 될 것이다.

 

4. arr[3]이 0이 된다는 뜻은 right에 남아있는 원소가 하나도 없다는 뜻이다.

(arr[3]dl 음수가 된 것은 left에서 카운트 했기 때문이고, Math.abs(arr[3])개가 right에 남아있는 arr[3]의 개수이다.)

 

5. left의 카운트가 right와 같을때마다 양쪽의 고유 원소 개수가 같으므로 answer++을 해준다.

 

 

- 코드 5ms

class Solution {
    public int numSplits(String s) {
        int[] arr = new int[26];
        int answer = 0;
        int left = 0;
        int right = 0;

        for(char ch : s.toCharArray()) arr[ch-97]++; // 0. 배열을 활용

        for(int i : arr) if(i > 0) right++; // 1. 중복되지 않은 모든 알파벳 수를 right에 저장.

        for(char ch : s.toCharArray()) {
            if(arr[ch-97] > 0) { // 2. left에서 체크하였다는 뜻으로 음수변환
                left++;
                arr[ch-97] = -arr[ch-97] + 1;
            } else if(arr[ch-97] < 0) { // 3
                arr[ch-97]++; // 음수에서 0이 될수록 right에서 현재 원소가 줄어드는 것
            }

            if(arr[ch-97] == 0) right--; // 4

            if(left == right) answer++; // 5
            else if(left > right) break;
        }

        return answer;
    }
}

 

딱 이 문제만 가지고 이야기하는 지엽적인 설명이 의미가 있나 싶기도 하다..

 

이 문제에서 얻을 수 있는 중요한 가치는

정수를 양수, 음수로 바꿔가며 활용하는 방법은 결국 boolean배열을 추가하지 않고 정수배열을 활용할때 유용하다는 것과,

https://1years-shsh.tistory.com/57 에서 다뤘었던 일차원배열을 활용하여 등장빈도를 세는 법이라고 생각한다.

 

 

 

- 코드(폐기된) 33ms

class Solution {
    public int numSplits(String s) {
        Map<Character, Integer> map = new HashMap<>();
        Set<Character> set = new HashSet<>();
        int answer = 0;

        for(char c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        for(char c : s.toCharArray()) {
            if(map.containsKey(c)) { // 전체에서 첫 원소를 빼므로 right 시작
                if(map.get(c) > 1)  map.put(c, map.get(c)-1);
                else map.remove(c);
            }
            set.add(c); // 첫 원소를 추가하였으므로, left 시작
            if(set.size() == map.size()) answer++;
        }

        return answer;
    }
}

 

이 문제에서는 좋지 않지만

다른 어떤 문제에서는 좋은 코드가 될 것 같기도 해서 올려본다..

 

 

 

https://leetcode.com/problems/number-of-good-ways-to-split-a-string/

Number of Good Ways to Split a String - LeetCode