[문자열] 문제 이름 : String Reduction

문제 설명

알파벳 소문자로 이루어진 문자열이 주어질 때 해당 문자열의 부분 문자열이 모두 서로 다르도록 문자열을 줄일 때 최소 삭제 횟수를 구해라(문자열의 아무 index 삭제 가능) 

 

사용 개념

문자열, 반복문

 

문제 해결 아이디어 

부분문자열의 경우 문자 1개도 부분 문자열에 해당한다. 즉 부분 문자열이 서로 다르도록 하려면, 문자열에서 각 알파벳이 1개만 존재해야 한다. 따라서 최소 삭제의 경우는 2개 이상 존재하는 알파벳들을 1개 빼고 모두 삭제하면 된다. 

 

코드 

구현 방식)

ㄱ. 알파벳 등장 횟수 저장을 위한 int 배열 선언(index 0 = a, index 1 = b . . .)

ㄴ. String 클래스의 charAt()을 사용해 각 문자 접근

ㄷ. 각 알파벳에 해당하는 ㄱ에서 생성한 배열의 index를 찾음(Char to Int) 

ㄹ. 빈도수가 0인 경우 빈도수 1 증가시키기

      빈도수가 0이 아닌 경우 삭제 

class Result {
    /*
     * Complete the 'getMinDeletions' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts STRING s as parameter.
     */
    public static int getMinDeletions(String s) {
        int alphabet[] = new int[26]; // ㄱ
        int countDelete = 0;
        for(int i = 0; i < s.length(); i++){
            char val = s.charAt(i); // ㄴ
            int index = val - 'a'; // ㄷ
            if(alphabet[index] == 0) // ㄹ
                alphabet[index]++;
            else
                countDelete++;
        }
        return countDelete;
    } 
}

시간 복잡도) O(N) 

위의 코드에서 for문은 문자열의 길이(N)만큼 반복되므로 N에 비례하여 연산이 수행된다. 

 

추가 개념 정리

* 아스키코드를 사용해 Char ➔ Int로 변환하기

→ 컴퓨터는 문자를 기억할 수 없기 때문에 숫자에 문자를 연결함

→ 아스키코드값 = 문자를 1:1로 대응시킨 숫자

     ex) 문자 'a'의 아스키코드값 97, 'b'의 아스키코드값 98 

→ 아스키코드값으로 연산을 수행하면 char를 int로 변환한 것과 동일한 결과 나옴 

int val = 'b' - 'a'; //98 - 97
System.out.println(val); //1

 

참고)

https://frhyme.github.io/java/java_basic02_char_to_int/

https://m.blog.naver.com/qkrghdud0/220855660291