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배 정도의 효율..

 

비트 연산자 자체가 생소해서 어려웠는데 이해만 잘 한다면 다른 문제에서도 활용이 쉽게 될 것 같아서 꼭 배워놓자

 

전공자가 아니라 진수와 비트에 관해 조금 약한 걸 확실하게 느꼈고 기초부터 다져야겠네

 

정처기 준비중이라 확실하게 익혀두면 좋을 것 같긴 해