[코드포스 Practice5] D. K-Dominant Character

문제 짧아서 아싸링 했는데 무슨 뜻인지 몰라서 넘어갔음ㅋㅋㅋㅋ

번역도 해보려 했는데 아니 이게 무슨 말이지?? 싶었다. c가 포함된 길이의 최솟값 <- 여기서 c ?? 아무 문자나 다 되는건가?? 엥?? 음?? 엄?? 최소 문자열의 길이가 k인데 k의 최솟값을 찾으라고? (멘붕중)

 

그래서 예시 보면서 힌트를 얻으려고 했었다. 뭔가 abacaba -> 2 이고 zzzzz -> 1 이므로 아 그럼 가장 가까운 문자의 길이를 구하는 거구나!싶었는데 abcde가 3인 거 보고 어.. 버버.. 버..  패스했다. 계속 왜 5가 아니지 싶었음

 

---

이거 다시보니깐 그문제였다. 파라메트릭 서치!!! 반가웠음. 사실 정말 반가운 건 아니고 그냥 아는 거 나와서 조건반사적 반가움이었다. 파라메트릭 서치랑은 아직 낯선 사이임,, 

 

이렇게 생각했는데 자꾸 어디서 문제가 생겨서 확인해봤더니 이 부분이 문제였다. 

이거 a.size()여야 하는데 s.length()로 해서 z 넣으니 값이 이상하더라

 

#include <iostream>
#include <string>
#include <vector>
using namespace std;

bool isOk(string s, int mid){
    vector<int> a(26, 0);
    int i;
    for(i = 0; i <= s.length() - mid ; i++){
        for(int j = i; j < i+mid; j++){
            if(a[s[j]-'a'] == i)
               a[s[j]-'a'] = i+1; 
        }
    }
    for(int j=0; j<a.size(); j++){
        if(a[j] == i)
            return true;
    }
    return false;
}

int main() {
    string s;
    cin >> s;
    
    int lo = 1;
    int hi = s.length();
    
    //이거 다시 확인해야함
    int ans;
    
    while(lo <= hi){
        int mid = (lo + hi) / 2;
        
        if(isOk(s, mid)){
            hi = mid - 1;
            ans = mid;
        }
        else{
            lo = mid + 1;
        }
    }
    
    printf("%d", ans);
}

완성~~

하지만 시간초과~~

 

 

길이봐 장난해요 코드포스?

(하지만 문제에 문자열 길이 10만이라 알려줬다구)

 

 

아ㅋㅋㅋㅋ

근데 왜 틀린줄 알겠다. 

이분탐색을 쓰면 뭐해 함수에서 n^2을 쓰는데ㅋㅋㅋㅋ

ㅋㅋ

ㅋㅋㅋ

으악! 다시 고쳐야겠다!

 

출처 : 즈우북님

아 N^2이 만까지 가능한데 내 코드는 (logN) * (N^2)이라 백퍼 터지는구나

 

아니 그런데 이거 제한이 2초인데???

아 그럼 N^2이 2만까지 가능한건가? 그래도 터지겠네 

---

그다음 생각해본 게 이거..

 

먼저 첫 덩어리에 있는 알파벳을 다 세어준다. 알파벳이 있다면 1로 

다음으로 다른 덩어리들을 확인하는데 그 덩어리에 a부터 z까지 있는지 확인한다. 해당 알파벳이 없다면 a배열의 해당 인덱스를 0으로 만들어준다. 

 

이 반복문 돌면 덩어리 속에 계속 남아있는 알파벳은 그대로 1일꺼고 한 번이라도 없으면 0일 것이다. 

남아있는 알파벳이 없으면 a배열이 전부 0이므로 그때는 check와 같아진다. -> false 반환

 

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

bool isOk(string s, int mid){
    vector<int> a(26, 0);
    vector<int> check(26, 0);
    
    printf("%d", mid);
    for(int i = 0; i < mid; i++){
        a[s[i]-'a'] = 1;
    }
    
    for(int i = 1; i <= s.length() - mid ; i++){
        for(int j = 'a'; j <= 'z'; j++){
            char c = *lower_bound(s.begin()+i, s.begin()+mid+i-1, j);
            if(c != j) 
                a[j-'a'] = 0;
        }
    }
    
    
    printf("\n");
    
    if(check == a){
        printf("false");
        return false;
    }
    printf("true");
    return true;
}

int main() {
    string s;
    cin >> s;
    
    int lo = 1;
    int hi = s.length();
    
    //이거 다시 확인해야함
    int ans = -999;
    
    while(lo <= hi){
        int mid = (lo + hi) / 2;
        
        if(isOk(s, mid)){
            hi = mid - 1;
            ans = mid;
        }
        else{
            lo = mid + 1;
        }
        
        printf("\n\n");
    }
    
    printf("%d", ans);
}

 

이렇게 짰는데.. 맞는 거 같은데.. 예제 하나가 맞지 않다. 

 

4일때 true여야 하는데 false가 떴다. 다른 예제는 맞게 나온다..

이대로 돌아가면 처음 이분탐색 logN, 함수 안에서 반복문*이분탐색 = N*log^2N 정도니 시간초과도 안 걸릴 것 같은데.. 어디서 틀렸지

 

 

오늘 D, E 다 풀려 했는데 결국 D 못 해결했음.. 좀 더 생각하면 답 알 수 있을 것 같은데 이제 지침ㅠ 내일 다시 봐야지

 

---

 

위의 문제 틀린 이유가 lower_bound는 정렬된 배열에서만 값을 찾아준다. 만약 정렬되지 않았다면 어떤 값을 반환할지 알 수 없다ㅋㅋㅋ 정렬 안 해줘도 찾아주는 줄 알았음 (머쓱,,) 그래서 그냥 find 함수로 찾아버릴까 했는데 얘를 쓰면 다시 시간복잡도가 n 제곱이 되어버림ㅎㅎ..ㅎㅎ

 

다음 방법! 너무 신기한 걸 알았다. 

맨 처음 부분 배열에 있는 문자 개수를 알면 다음 부분 배열에 있는 문자 개수는 O(1)에 구할 수 있다. (아니 어떢게?)

저 규칙을 보면 중간 하늘색 부분은 똑같고 앞의 배열(i-1번째)이 없어지고 뒤의 배열(i+mid-1 번째)가 추가된다. 이 두개만 알면 다음 배열에 있는 문자 개수를 알 수 있다. 시간복잡도가 O(1) !!! 와 정말 신기하다. 

 

이걸 이용해서 isOk() 함수를 구현했다.

처음에 배열 두개를 만들어서 하나는 문자 개수를 세고 다른 하나는 해당 문자가 계속 있는지 체크한다. 다음으로 첫 덩어리를 읽어서 문자 개수를 센다. 그리고 나타난 문자는 check 배열에 1로 만들어준다. 다음으로 덩어리를 이동시키면서 개수를 더하고 빼는데 이 때 개수가 한 번이라도 0이 되면 check 배열의 값을 0으로 만들어준다. 

 

마지막으로 모든 과정이 다 끝나면 check 배열을 확인한다. check 배열에 1이 있으면 그 문자는 계속 나타난 것이므로 true를 반환한다. 만약 check 배열에 1이 없으면, 즉 전부 0이라면 그때는 false를 반환한다. 

 

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

bool isOk(string s, int mid){
    vector<int> v(26, 0);
    vector<int> check(26, 0);
    vector<int> zero(26, 0);
    
    for(int i = 0; i < mid; i++){
        v[s[i]-'a']++;
        check[s[i]-'a'] = 1;
    }
    
    for(int i = 1; i <= s.length() - mid ; i++){
        v[s[i-1]-'a']--;
        v[s[i+mid-1]-'a']++;
        
        if(v[s[i-1]-'a'] <= 0)
            check[s[i-1]-'a'] = 0;
    }    
    
    if(zero == check)
        return false;
    return true;
}

int main() {
    string s;
    cin >> s;
    
    int lo = 1;
    int hi = s.length();
    
    //이거 다시 확인해야함
    int ans = -999;
    
    while(lo <= hi){
        int mid = (lo + hi) / 2;
        
        if(isOk(s, mid)){
            hi = mid - 1;
            ans = mid;
        }
        else
            lo = mid + 1;
    }
    printf("%d", ans);
}

코드는 위와 같다. 

 

맞았다ㅎㅎ

이제 E번 풀러 가야지