2016년 5월 10일 화요일

10465 - Rolling Encryption

https://www.acmicpc.net/problem/10465

이전 $k$의 길이만큼에서 가장 많이 출현한 알파벳만큼 shift한다. 오른쪽으로 이동하면서 이전 길이 $k$만큼의 빈도를 계속 갱신했다. $k \le 10,000$와 $c \le 100,000$가 생각보다 커서 라인 스위핑하듯이 했다. 이걸 스위핑이라고 해도 될지 모르겠다.

#include <bits/stdc++.h>
using namespace std;

int fq[26];
int shiftBy(){
    int c=0, maxFq=-1;
    for(int i=0; i<26; ++i){
        if(maxFq < fq[i]){
            maxFq = fq[i];
            c = i+1;
        }
    }
    return c;
}

int main(){
    int k;
    char s[1000001];
    scanf("%d %s", &k, s);
    for(int i=0; s[i]; ++i){
        if(i < k) putchar(s[i]);
        else {
            printf("%c", (s[i]-'a'+shiftBy())%26+'a');
            fq[s[i-k]-'a']--;
        }
        fq[s[i]-'a']++;
    }
    return 0;
}
댓글 쓰기

게시글 목록