3223. Minimum Length of String After Operations

https://leetcode.com/problems/minimum-length-of-string-after-operations/

 

3223. 작업 후 문자열의 최소 길이

 

이번 문제의 경우에 중간 난이도인데  생각하기에 따라 쉬운 문제일 수도, 어려운 문제일 수도 있다.

내 경우에는 처음에 너무 복잡하게 생각해서 시간초과로 몇번 틀렸지만 결국 힌트를 보고 빠르게 풀어냈다.

 

문자열 s가 주어집니다.
다음 프로세스는 s에서 원하는 만큼 수행할 수 있습니다.

- 인덱스 i의 왼쪽에 s[i]와 동일한 문자가 하나 이상 있고
  오른쪽에도 s[i]와 동일한 문자가 하나 이상 있도록 문자열에서 인덱스 i를 선택합니다.
- s[i]와 동일한 인덱스 i의 왼쪽에서 가장 가까운 문자를 삭제합니다.
- s[i]와 동일하고 인덱스 i 오른쪽에 가장 가까운 문자를 삭제합니다.

달성할 수 있는 최종 문자열 s의 최소 길이를 반환합니다.

예 1:
입력: s = "abaacbcbb"
출력: 5
설명: 다음 연산을 수행합니다.
- 인덱스 2를 선택한 다음 인덱스 0과 3에서 문자를 제거합니다.
- 결과 문자열은 s = "bacbcbb"입니다. 인덱스 3을 선택한 다음 인덱스 0과 5에서 문자를 제거합니다.
- 결과 문자열은 s = "acbcb"입니다.

예 2:
입력: s = "aa"
출력: 2
설명: 아무 연산도 수행할 수 없으므로 원래 문자열의 길이를 반환합니다.

제약 조건: 1 <= s.length <= 2 * 105s는 소문자 영어 문자로만 구성됩니다.

 

이 문제를 보자마자 나는 나만의 풀이 방식을 먼저 작성하고 코드를 작성했다.

1. s의 첫 문자부터 순서대로 검사한다.
2. 만약 이미 검사한 문자가 나오면 그 위치를 i로 정한다.
3. 앞으로 탐색하여 현재 위치의 문자와 같은 문자를 찾는다.
4. 만약에 앞에 동일한 문자가 있다면 이전 문자와 해당 문잘
5. 삭제된 문자열을 제외하고 다시 정렬한 다음 반복한다.
6. 더 이상 반복할 수 없다면 문자 개수를 반환한다.

 

주어진 문자열을 배열로 바꿔서 탐색한 다음 만나는 글자들을 비교해서 지우고,

최종적으로 배열의 개수를 반환하도록 설계했었다.

그리고 예전에 코테 공부를 할때 사용했던 재귀함수가 생각나서 그것을 응용해보려고 했다.

class Solution {
    public int minimumLength(String s) {
        int result = 0;

        // 초기 배열 생성
        char[] c = s.toCharArray();
        result = aa(c);

        return result;
    }
    // 재귀함수 생성
    public static int aa(char[] c){
        for(int i = 0; i < c.length; i++){
            if(0 <= i-1){ // 이전값이 있다면
                for(int j = 0; j < i; j++){
                    // 같은 값이 있고 마지막이 아니라면
                    if(c[j] == c[i] && i < c.length-1){
                        // 앞 자리에서 같은 값이 있는지 확인
                        // k에 현재 위치값+1 넣고 반복
                        for(int k = i+1; k < c.length; k++){
                            if(c[k] == c[i] && c[k] == c[j]){
                                char[] re = new char[c.length-2];
                                int count = 0;
                                // 배열에서 값 제거
                                for(int l = 0; l < c.length; l++){
                                    if(j == l || k == l){
                                        continue;
                                    }else if(count == c.length-2){
                                        break;
                                    }
                                    re[count] = c[l];
                                    count++;
                                }
                                return aa(re);
                            }
                        }
                    }
                }
            }
        }
        return c.length;
    }
}

 

일단 테스트 케이스 1,2,3 까지는 맞았는데 이후에 나오는 테스트 케이스들은 시간 초과로 모두 실패했다.

지금 다시봐도 너무 복잡하고 왜 이렇게까지 했어야 했나 싶은데

그래도 이렇게 코드를 짜면서 재귀함수 작성법을 다시 익힐 수 있었다.

 

이후에 어떻게 풀어야 할까 고민하다 힌트를 봤는데,

힌트에는 이렇게 써져있었다.

힌트 1
답변을 찾는 데 있어 각 캐릭터의 유일한 중요합니다.

힌트 2
문자가 3 회에 발생하면 프로세스를 수행할 수 없습니다.

힌트 3
문자열에 3번 이상 발생하는 문자가 있다고 가정하면 최대 2개의 문자가 남을 때까지 이 문자 중 2개를 반복해서 표시할 수 있습니다.

 

이걸 보고 머리를 한 대 맞은 느낌이었다.

정답은 정수를  반환하면 되는 건데... 그리고 모든 문자열에서 같은 문자가 3개 이상 존재할 수 없는데...

 

그래서 바로 모든 코드를 지우고 다시 처음부터 생각해 보았다.

그 결과 이런 결론이 도출되었다.

문자열의 빈도수를 세시오
   -> 해당 문자가 3개 이상 있는가?
         -> 예
              -> 그렇다면 /3을 하시오
         -> 아니오
              -> 그렇다면 다음 문자에 대한 계산을 하십시오
  -> 최종적으로, 모든 문자의 개수가 3개 미만일 때 총개수를 출력하시오

 

이렇게 생각을 정리하고 다시 코드를 작성하니 좀 더 깔끔하고 더 빠르게 작성이 가능했다.

그리고 중간중간 디버깅 하면서 내가 틀린 부분을 다시 수정해 나갔다.

class Solution {
    public int minimumLength(String s) {
        int result = 0;
        
        int[] tempIndex = new int[26];

        // 초기 배열 생성 (빈도수 측정)
        for(char ch : s.toCharArray()){
            tempIndex[ch - 'a']++;
        }
        
        // a-z까지 반복
        for(int a : tempIndex){
            int temp = 0;
            // 3보다 크다면
            if(a >= 3){
            	// 나눈 값이 3보다 크다면
                if((a/3) + (a%3) >= 3){
                    temp = (a/3) + (a%3);
                    // 3보다 작아질때 까지 반복
                    while(true){
                        temp = (temp/3+temp%3);
                        if(temp < 3){
                            break;
                        }
                    }
                    result += temp;
                }else{
                    result += (a/3) + (a%3);
                }
            }else{
                result += a;
            }
        }
        return result;
    }
}

 

이렇게 작성하여 제출하였더니

런타임 10ms, 메모리 46.3MB로 양호한 성적이 나왔다.

 

이번 문제를 풀어보면서 느낀점은

머릿속이 복잡해질땐 과감하게 모두 지우고 환기시킨 다음

다시 간단하게  생각해 보는 게 참 중요하다는 생각이 든다.