[코테연습] 2405. Optimal Partition of String

- 탐욕법
- 문제 분석
 1. 문자열이 주어진다.
 2. 문자열을 자른다.
 3. 이때 자르는 기준은 문자가 중복되지 않도록 하는 것.
 4. 예를 들면, abaca 가 있을 경우, ab ac a 로 잘라야 같은 문자가 중복되지 않는다.


 - 문제풀이
 1. 특정 문자를 toCharArray() 로 자른다. 
 2. char[] 를 선언하여 for 문으로 반복한다.
 3. 반복문을 시행하면서 같은 문자가 반복되었는지 확인하기 위해 boolean[] visited 배열을 선언한다.
   3-1. boolean[] visited 배열의 최대 length 는 100 으로 선언한다.
   3-2. char[] 가 반복하면서 알파벳의 값이 최대 100을 넘으므로, 가장 작은 숫자에 해당하는 알파벳 'a' 를 차감한다.
   3-3. visited[ch] 로 확인한다.
 4. 반복되었다면, 다시 해당 문자로 돌아간다.
   4-1. 돌아갈때, 총 count 값을 더한다.
   4-2. visited 는 초기화하여 다시 중복 값을 확인한다.

 

class Solution {
    public int partitionString(String s) {
        char[] charArr = s.toCharArray();
        int count = 1;
        boolean[] visited = new boolean[100];
        for (int i = 0; i < charArr.length; i++) {
            int ch = charArr[i] - 'a';
            if (!visited[ch]) {
                visited[ch] = true;
            } else {
                count++;
                i--;
                visited = new boolean[100];
            }

        }
        return count;
    }
}