Today I Learned

오늘 할일
1. LeetCode
2. 생각정리

오늘 한일
1. LeetCode

• 지난번부터 최적화에서 막혀있는 1456번 문제를 다시한번 분석해보려고 한다. 이 문제는 문자열 s와 정수 k가 주어지면 k슬라이딩 윈도우 범위 내에서 모음이 가장 많이 나온 개수를 반환하는 문제이다.
  이 문제의 어려운 점은 최적화인데, 일반적으로 생각할 수 있는 중첩반복의 경우로는 최적화를 진행해도 별 효과가 없었다. 106개의 테스트 케이스 중 103번애서 막힌 가장 좋은 성과의 코드는 아래와 같았다.

  		String vowels="aeiou";
         int size=s.length();
         int count=0;
         int max=0;
  
         for(int i=0; i<size-k+1; i++){
             if(i<size-k && vowels.indexOf(s.charAt(i))==-1)
                 continue;
             count=0;
             for(int j=0; j<k; j++){
                 if(vowels.indexOf(s.charAt(i+j))!=-1){
                     count++;
                 }
             }
             if(count>max) {
                 max = count;
             }
         }
         return max;

  103번째 테스트 케이스는 정말 긴 문자열이 주어진다. 위의 알고리즘 틀에서 최적화를 시도해보았지만, 103번을 넘지 못했기에 다른 알고리즘을 고안했다.

시도해볼 방법은 다음과 같다. 모음이 있는 인덱스들을 따로 저장한 뒤에, 모음의 위치 인덱스로만 최대 모음 개수를 계산하는 방식이다. 시도한 코드는 아래와 같다.

class Solution {
    public int maxVowels(String s, int k) {
        String vowels="aeiou";                      //모음 모음ㅋㅋ
        int size=s.length();                        //문자열 길이
        char[] s_c=s.toCharArray();                 //char[]형변환           

        List<Integer> idx_vowel=new ArrayList<>();  //모음의 인덱스를 저장
        for(int i=0; i<size; i++){
            if(vowels.contains(""+s_c[i])){
                idx_vowel.add(i);
            }
        }

        int num;
        int max=0;
        int idx_vowel_size=idx_vowel.size();
        for(int i=0; i<idx_vowel_size-1; i++){        //탐색의 시작 기준 i
            num=1;                                  //k범위 내의 모음 개수를 저장할 num. 이미 한개는 발견한 것
            int elem_i=idx_vowel.get(i);
            for(int j=1; j<k && i+j<idx_vowel_size; j++){
                int elem_j=idx_vowel.get(i+j);
                if(elem_j-elem_i<k){
                    num++;
                } else{
                    break;
                }
            }
            if(max<num)
                max=num;
        }
        return max;
    }
}

그 결과 처음으로 103번째 테스트케이스를 통과하여 104번으로 넘어갔다. 104번 테스트는 모음이 없는 경우 0을 리턴해야하는 케이스인데, 현재 모음이 있는 인덱스들이 없는 경우를 예외처리해주지 않았기 때문에 최초에 모음들의 인덱스 계산시, 저장된 리스트의 크기가 0이면 0을 리턴하게 코드를 추가해주었다.
그 결과 마찬가지로 오답처리가 되었다. 그 이유는 tryhard에 모음이 딱 한개 있기 때문이다. 이 또한 리스트 크기가 1이면 1을 리턴하게끔 코드를 추가해주었다.

그 결과 104번 테스트 케이스틑 통과가 되었지만 모음으로 가득찬 문자열이 입력된 경우 Time Limit Exceeded가 발생하는 것을 볼 수 있었다. 이 또한 모음으로 가득차있을 경우 k를 리턴하게 예외처리를 해주자..보다는 슬라이드가 꽉 찬 경우가 존재할 경우 k를 리턴하게끔 예외처리를 범용적으로 해주자.

class Solution {
   public int maxVowels(String s, int k) {
       String vowels="aeiou";                      //모음 모음ㅋㅋ
       int size=s.length();                        //문자열 길이
       char[] s_c=s.toCharArray();                 //char[]형변환           

       List<Integer> idx_vowel=new ArrayList<>();  //모음의 인덱스를 저장
       for(int i=0; i<size; i++){
           if(vowels.contains(""+s_c[i])){
               idx_vowel.add(i);
           }
       }

       int num;
       int max=0;
       int idx_vowel_size=idx_vowel.size();

       if(idx_vowel_size==0)
           return 0;
       if(idx_vowel_size==1)
           return 1;

       for(int i=0; i<idx_vowel_size-1; i++){        //탐색의 시작 기준 i
           num=1;                                  //k범위 내의 모음 개수를 저장할 num. 이미 한개는 발견한 것
           int elem_i=idx_vowel.get(i);
           for(int j=1; j<k && i+j<idx_vowel_size; j++){
               int elem_j=idx_vowel.get(i+j);
               if(elem_j-elem_i<k){
                   num++;
               } else{
                   break;
               }
           }
           if(max<num)
               max=num;
           if(max==k)
               return max;
       }
       return max;
   }
}

앗쌍