99클럽 코테 스터디 31일차 TIL [LeetCode] Optimal Partition of String (Java)

📃 문제

[LeetCode] Optimal Partition of String

🖋️ 풀이

그리디 알고리즘 문제

• 주어진 문자열 s를 순회한다.
• 이미 partition에 해당 문자가 존재한다면, 새 파티션을 시작한다.
• 문자를 파티션에 추가한다.
• 반복문을 빠져나오면, 마지막 파티션을 카운트하고 그 수를 반환한다.

✅ 정답 코드

class Solution {
    public int partitionString(String s) {
        Set<Character> partition = new HashSet<>();
        int cnt = 0;

        for(char c : s.toCharArray()) {
            if(partition.contains(c)) {
                cnt++;
                partition.clear();
            }
            partition.add(c);
        }

        cnt++;
        
        return cnt;
    }
}

🔍 다른 풀이

Set을 사용하지 않고 배열을 사용

• 각 문자의 등장 여부를 boolean 배열에 저장한다.
• 이미 이 파티션에 등장한 문자라면, 새 파티션을 시작한다.

class Solution {
    public int partitionString(String s) {
        boolean[] partition = new boolean[26];
        int cnt = 0;

        for (int i = 0; i < s.length(); i++) {
            if (partition[s.charAt(i) - 'a']) {
                cnt++;
                partition = new boolean[26];
            }
            partition[s.charAt(i) - 'a'] = true;
        }

        
        cnt++;

        return cnt;
    }
}

• 배열을 이용한 풀이가 24ms 더 빠른 성능을 보인다.