99클럽 코테 스터디 40일차 TIL Optimal Partition of String
https://leetcode.com/problems/optimal-partition-of-string/description/
비트연산자
map
1. 문제 및 접근
2405. Optimal Partition of String
주어진 s의 서브 스트링을 구성하는데, 중복된 char가 없게 만들어야 한다
최소의 subString 갯수를 반환
"abacaba" 라면 "ab" "ac" ,"aba"로 나눴다면 aba에서 a가 2개라 안됨
s = abacaba 라면 앞에서부터 시작해서 있는 수 중 같은 수가 들어오면 그전까지 담기 ?
각 substring은 중복되도 되는 듯 하다
Constraints:
- 1 <= s.length <= 10^5
- s consists of only English lowercase letters.
2. 풀이
public int partitionString(String s) {
int count = 0;
HashMap<Character, Integer> map = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char current = s.charAt(i);
//현재 current가
// map에 없으면 넣고 다음수
// map에 있다면 count++해주고, map을 초기화하고 다시 담기
if (!map.containsKey(current)) {
map.put(current, 1);
} else {
count++;
map = new HashMap<>();
map.put(current, 1);
}
}
return count +1; // 마지막 subString이 하나 남아있으니 그 수 +1
}
s = "abacaba" 라면
앞에서부터 시작해서 있는 수 중 같은 수가 들어오면 그전까지 담아서 세어주면 될 것 같다.
그리디 알고리즘으로 접근
2-1. map으로 subString 담기
set으로 관리해줘서 사이즈끼리의 차이를 비교할까 ? 하다가 그냥 map으로 한번 해보자 싶었다.
우선 subString들이 나올 때 마다 새로운 hashmap에 담을꺼라,
count 변수와
subString들을 담을 Character, Integer 타입의 map 선언
2-2. subString 구분하기
현재 String의 char를 current에 담아주고,
2가지로 나눠서 동작
1. subString으로 구성된 map에 이미 없는 current가 들어온다면 ?
- map에다가 저장하고 다음 current 판별
2. subString으로 구성된 map에 이미 담긴 current가 들어온다면 ?
- 이미 만들어진 map을 완성시킴을 의미하는 count++;
- 새로운 subString의 map을 만들어주기
- 다시 새로운 map에다가 current를 put
마지막으로 만들어진 subString은 반복문을 타서 count에 더해지지 않기 때문에 +1
실제 예로 보자면,
String s = "abacaba" 의 경우이고
편하게 생각하기 위해 subString으로 구성된 answer배열을 예시로 하나 들겠다
1.s = "abacaba", s.charAt(0) = 'a', map = [], count = 0, answer =[]
- a는 map에 없기에, map에 추가
결과 map = [a=1], count = 0, answer =[]
2. s ="abacaba", s.charAt(1) = 'b' , map = [a=1], count = 0, answer =[]
- b는 map에 없기에, map에 추가
결과 map = [a=1,b=1], count = 0, answer =[]
3. s ="abacaba", s.charAt(2) = 'a' , map = [a=1,b=1], count = 0, answer =[ab]
- a는 map에 있다
- count 세어주기
- 새로운 subString을 뜻하는 map 새로 초기화 후 a 담기
결과 map = [a=1], count = 1, answer =[ab]
4.s ="abacaba", s.charAt(3) = 'c' , map = [a=1],count = 1, answer =[ab]
- c는 map에 없기에, map에 추가
결과 map = [a=1,c=1], count = 1, answer =[ab]
5.s ="abacaba", s.charAt(4) = 'a' , map =[a=1,c=1],count = 1,answer =[ab]
- a는 map에 있다
- count 세어주기
- 새로운 subString을 뜻하는 map 새로 초기화 후 a 담기
결과 map = [a=1], count = 2, answer =[ab, ac]
6.s ="abacaba",s.charAt(5) = 'b' , map =[a=1],count = 2,answer =[ab, ac]
- b는 map에 없기에, map에 추가
결과 map = [a=1, b=1], count = 2, answer =[ab, ac]
7.s ="abacaba", s.charAt(6) = 'a' , map =[a=1,b=1],count = 2,answer =[ab, ac]
- a는 map에 있다
- count 세어주기
- 새로운 subString을 뜻하는 map 새로 초기화 후 a 담기
결과 map = [a=1], count = 3, answer =[ab, ac, ab]
마지막으로 [ab, ac, ab]가 배열에 담겨있고, 혼자 남은 map에는 a가 담겨 있다.
우리가 원하는 건
answer = [ab,ac,ab,a]인데, a를 담지 않았고, 마지막 남은 하나의 subString이니
count에 +1을 해줘서 원하는 값을 만들기!
3. 비트마스크 풀이법(feat. gpt)
public int partitionString1(String s) {
int count = 0;
int mask = 0; // 비트마스크를 초기화합니다.
for (int i = 0; i < s.length(); i++) {
int currentBit = 1 << (s.charAt(i) - 'a'); // 현재 문자의 비트를 설정합니다.
if ((mask & currentBit) != 0) { // 현재 문자가 이미 비트마스크에 있는지 확인합니다.
count++; // 새로운 부분 문자열을 시작해야 하므로 count를 증가시킵니다.
mask = 0; // 비트마스크를 초기화합니다.
}
mask |= currentBit; // 현재 문자를 비트마스크에 추가합니다.
}
return count + 1; // 마지막 부분 문자열을 포함하기 위해 1을 추가합니다.
}
gpt형님이 좋은 풀이를 하나 알려주셨다.
3-1 . 비트마스크 설정
s.charAt(i)번째 문자가 'a'랑 얼마나 떨어져 있는지를 판별해서 저장 ex) a = 0, b=1
1 << (s.charAt(i) - 'a')의 의미
(s.charAt(i) - 'a') 만큼 왼쪽으로 시프트한다.
이 연산은 해당 위치의 비트를 1로 설정하는 비트마스크를 생성하는 의미
a = 97이다
- 만약 s.charAt(i)가 'a'라면:
- 'a' - 'a'는 0
- 1 << 0은 1 (이진수로 00000001).
- 만약 s.charAt(i)가 'b'라면:
- 'b' - 'a'는 1
- 1 << 1은 2 (이진수로 00000010).
- 만약 s.charAt(i)가 'c'라면:
- 'c' - 'a'는 2
- 1 << 2은 4 (이진수로 00000100).
3-1. mask 안에 currentBit가 있다면?
mask와 현재 bit s.charAt(i)가 and연산자로 0이 아니라면 ?
(mask와 현재bit 둘다 가지고 있다면)
현재 mask 안에 s.charAt(i)가 들어있다는 뜻이다.
count++ 해주고,
subString인 mask를 초기화해주기 !
예시)
SubString = "abc" 라면 ? mask는 00000111 (a, b, c 각각의 비트가 1로 설정됨)
현재 문자가 'b'일 때:
- currentBit는 00000010
- mask & currentBit는 00000111 & 00000010이므로 00000010
- 이는 0이 아니므로, 'b'가 이미 부분 문자열에 포함되어 있음을 의미
3-2. mask 안에 currentBit가 없다면?
|= 의미 ?
mask에 현재 currentBit를 추가하는 비트 OR 연산
예시)
subString = "ac"라면 mask가 00000101이다.
현재 문자가 'b'라면 ?
- mask는 00000101 (현재 부분 문자열에 'a'와 'c'가 포함됨을 나타냄)
- 'b'의 비트마스크 값인 currentBit는 00000010
mask |= currentBit는 00000101 | 00000010이 되어 결과는 00000111
마지막으로 같은 이유로 +1 해주면 끝
엄청 줄었다..
4. 마무리
비트연산자와 map에 저장 후 순회의 성능 차이가 어마어마하다..
작은 데이터라 큰 시간 차는 없지만 단순히 보자면 5배 정도의 효율..
비트 연산자 자체가 생소해서 어려웠는데 이해만 잘 한다면 다른 문제에서도 활용이 쉽게 될 것 같아서 꼭 배워놓자
전공자가 아니라 진수와 비트에 관해 조금 약한 걸 확실하게 느꼈고 기초부터 다져야겠네
정처기 준비중이라 확실하게 익혀두면 좋을 것 같긴 해