문제 소개
"Number of Wonderful Substrings" 문제는 24년 4월 30일 Daily LeetCode Challenge 문제로 제시되었다. 'a'에서 'j' 사이의 문자로 이루어진 어떤 단어가 String 형식으로 주어졌을 때, 그 단어의 Wonderful Substring을 모두 구하는 문제이다. 어떤 String을 구성하는 문자가 홀수번 등장하는 경우가 최대 한 번일 때 Wonderful하다.
문제 풀이
brute-force 방식으로 substring으로 가능한 모든 경우의 수를 고려한다면, O(n^2)의 시간복잡도를 가지며 1 <= word.length <= 10^5인 경우 worst-case에서 100억번의 연산을 수행하게 된다. LeetCode에서 시간 초과에 해당한다.
오답노트
이 문제 풀이의 기반이 되는 세 가지의 직관이 있다.
-
prefix와 관련된 직관: 예를 들어,
String[2:5]는 String[:5]과 String[:1]라는 두 prefix의 차로 표현될 수 있다. -
bitmasking기법: 가능한 모든 조합의 Substring에 대해, a-j까지의 문자의 등장횟수의 홀짝여부만을 담아 비트마스킹으로 표현할 수 있다. 예를 들어, 한 문자가 홀수번 등장했을 때는 1 bit을 표시하고, 짝수번 등장했을 때는 0 bit로 표시할 수 있다. 이를substring 마스크라고 하자. 어떤substring 마스크가wonderful하려면, 마스크에 등장하는 bit의 개수가 0이거나 1이어야 한다.
이 두 직관을 결합할 수 있다. 모든 prefix에 대해 a-j까지의 문자의 등장횟수의 홀짝여부만을 표시한 마스크(이하 prefix 마스크)를 만들 수 있을 것이다. 그리고 어떤 substring 마스크를 구할 때, 이를 어떤 두 prefix 마스크로부터 구하는 연산이 존재할 것이다. 이 연산을 prefix 마스크 뺄셈이라고 부르자.
우리는 두 prefix 마스크에 담긴, 두 prefix를 구성하는 a-j까지의 문자의 등장횟수의 홀짝 정보로부터, prefix 마스크 뺄셈의 결과로 얻어진 substring 마스크가 어떻게 구성될지를 추측할 수 있다. 예를 들어, 만약 'a' 문자가 String[:5]에서 홀수번 등장하고, String[:1]에서 짝수번 등장했다면, 'a' 문자는 String[2:5]에서 홀수번 등장할 것이다. 왜냐하면 홀수에서 짝수를 빼면 홀수가 되기 때문이다. 따라서 String[:5]에 대한 prefix 마스크에서 'a'에 해당하는 비트가 1 bit이었고, String[:1]에 대한 prefix 마스크에서 0 bit였다면, String[2:5]에 대한 substring 마스크에서는 1 bit일 것이다. 마찬가지로, 홀수에서 홀수를 빼거나, 짝수에서 짝수를 빼면 짝수가 된다는 점을 이용해, 두 prefix 마스크에서 어떤 문자의 홀짝 여부에 해당하는 비트가 동일할 때는 substring 마스크에서 해당 비트는 0 bit이고, 비트가 다를 때는 1bit가 될 것임을 추측할 수 있다. 여기서 두 prefix 마스크에 대한 prefix 마스크 뺄셈 역할을 XOR 연산이 해 준다. XOR 연산은 같은 자리수에 위치한 두 비트가 동일할 때에는 그 자리수의 비트가 0 bit이고, 상이할 때에는 1 bit인 이진수를 반환하기 때문이다.
- HashSet과 관련된 직관
어떤 substring 마스크가 wonderful하려면, 마스크에 등장하는 bit의 개수가 0이거나 1이어야 한다. XOR 연산을 통해서 구해진 substring 마스크의 bit의 개수가 0이거나 1이려면, 두 prefix 마스크가 동일하거나, 혹은 단 하나의 자리에서 비트가 상이해야 한다. for loop을 돌면서 i(0<=i<=n-1)번째 등장하는 prefix에 대한 현재 prefix 마스크와 동일한 prefix 마스크가 이전 인덱스까지 총 몇 번 등장했는지를 HashSet에서 조회하여, 그 수만큼 wonderful substring의 개수가 더 있음을 계산할 수 있다. prefix 마스크를 키로 하여 O(1)의 시간 복잡도로 HashSet에 접근할 수 있으므로 시간 복잡도는 brute-force보다 개선된다. 마찬가지로, i번째 prefix 마스크에서 단 한 비트만 차이나는 prefix 마스크(문자의 종류는 a-j까지이므로, 10번의 생성 연산이 고정된다)이 HashSet에 각각 몇 개 있는지를 가져올 수 있다. for loop이 끝나면, 해가 나온다.
소감
세 가지 직관에 대해 모두 친숙할 수 있어야 풀 수 있는 문제였다. 문제 풀이에 가장 중요한 것은, n번 순회를 HashSet을 사용해서 O(1)으로 줄인 것이었다. 바로 전날 문제에 XOR 문제가 나왔었는데, 만약 HashSet에 대한 직관을 잘 떠울릴 수 있었다면 풀었을 수도 있었을 것 같다. 글로 풀어쓰면서 배울 수 있었다. 중간에 글이 날아갔는데, 다시 쓰느라고 힘들었다.
