LeetCode 1525 - Number of Good Ways to Split a String ( Java )

 

안녕하세요 besforyou입니다

 

이번 글은 LeetCode - 1525. Number of Good Ways to Split a String 문제 풀이입니다

 

---

문제 해설

 

문자열 s 가 주어진다.

 

문자열 s를 p와 q로 분리했을때, p와 q에 포함된 고유한 문자 개수가 동일하다면 good split이라고 한다.

 

good split의 개수를 구하라.

 

---

문제 풀이

 

HashMap을 이용한 풀이와 포인터와 변수를 이용한 풀이가 있습니다.

 

 

1. HashMap 

두 개의 hashmap left, right을 생성합니다.

 

문자열 s의 모든 문자를 key로 하고 문자의 개수를 value로 하는 key-value pair를 right hashmap에 저장합니다.

 

문자열 s의 문자를 처음부터 끝까지 참조하면서 left hashmap에 저장하는데, right hashmap에 동일한 문자 key가 존재한다면

해당 key의 value에 -1을 하고, value값이 음수가 되면 hashmap에서 제거합니다.

 

left hashmap과 right hashmap의 크기가 동일하면 good split으로 판단합니다.

 

// hashmap version
class Solution {
        public int numSplits(String s) {
 
            HashMap<Character, Integer> left = new HashMap<>();
            HashMap<Character, Integer> right = new HashMap<>();
 
            for ( int i = 0 ; i < s.length() ; i++ ) {
                char c = s.charAt(i);
                right.put(c, right.getOrDefault(c, 0) + 1);
            }
 
            int count = 0;
 
            for ( int i = 0 ; i < s.length() ; i++ ) {
                char curr = s.charAt(i);
 
                left.put(curr, left.getOrDefault(curr, 0) + 1);
                right.put(curr, right.getOrDefault(curr, 0) - 1);
 
                if (right.get(curr) <= 0) right.remove(curr);
                if (left.size() == right.size()) count += 1;
            }
 
            return count;
        }
    }
 

 

 

2. Two - pointer

원리는 hashmap 풀이와 동일합니다.

 

길이가 26인 정수형 배열 두 개 , 포인터 변수 두 개와 good split 갯수를 저장할 변수 res를 준비합니다.

 

문자열 s의 모든 문자를 배열에 저장하는데 인덱스를 [ 문자 - 'a' ] 로 하여 이상없이 저장되도록하고, 포인터를 증가시켜 배열안에 저장된 문자 개수를 저장하도록합니다.

 

문자열 s의 모든 문자를 처음부터 다시 참조하며 같은 방식으로 문자를 다른 배열에 저장하고 다른 포인터도 증가시키되, 이미 문자가 저장된 배열에서 해당 문자가 존재하면 문자의 개수와 포인터 값을 감소 시킵니다.

 

각각의 배열속 문자 개수를 저장하고 있는 포인터 변수를 비교하여 값이 같다면 res += 1

 

반복문이 끝나면 res를 반환합니다.

 

// faster solution : two-point
class Solution {
    public int numSplits(String s) {
        int rc[] = new int[26], lc[] = new int[26], l = 0, r = 0, res = 0;
        for ( char c : s.toCharArray() ) if ( rc[c - 'a']++ == 0 ) r++;
 
        for ( char c : s.toCharArray() ) {
            if (lc[c - 'a']++ == 0 ) l++;
            if (--rc[c - 'a'] == 0 ) r--;
            if ( l == r ) res++;
        }
 
        return res;
    }
}
 

 

---

결과 

 

1. Hashmap

 

 

 

2. Two - pointer

 

 

 

 

1번 방식이 구현히 간편하고 이해하기도 편하지만

2번 방식이 훨씬 빠르고 메모리도 덜 사용하므로 2번 방식을 사용하자.