BOJ 백준 16472번 고냥이

 

BOJ 백준 16472 고냥이

 

문제: https://www.acmicpc.net/problem/16472

16472번: 고냥이

 

문제에서 주어지는 문자열을 S라고 하자.  이 문제는 크게 두 가지 풀이가 있다. 하나는 인식할 수 있는 문자열의 길이를 가지고 이분 탐색(Binary Search)하는 것과 다른 하나는 두 포인터(Two Pointer)를 사용해서 푸는 것이다.

 

 

 

1. 이분 탐색으로 풀기

 

이분 탐색 대상을 인식할 수 있는 문자열의 길이로 설정한다. 즉, 길이 mid만큼 연속되는 문자열을 최대로 인식할 수 있다고 가정한다. 그리고 주어진 문자열에서 mid 길이만큼의 연속되는 부분 문자열을 탐색하면서 각 문자열을 인식하는 데 필요한 알파벳 종류의 최소 개수와 번역기가 인식 가능한 최대 알파벳 종류 수인 N을 비교한다. 다시 말해서, 길이 mid의 연속되는 부분 문자열에서 출현하는 알파벳 종류의 수 cnt가 N 이하이면 해당 부분 문자열을 읽을 수 있고, 그렇지 않으면 읽을 수 없다. 읽을 수 있는 부분 연속 문자열이 하나라도 존재하면 더 긴 길이도 읽을 수 있는지 구해야 하므로 left를 mid + 1로 이동하고, 그렇지 않으면 이보다 더 긴 문자열은 읽을 수 없으므로 right를 mid - 1로 이동하여 이분 탐색 과정을 이어간다. 

 

여기서 고려해야 할 부분은 연속되는 각 부분 문자열에서 쓰이는 알파벳 종류가 무엇인지를 구해야 한다는 것이다. 이는 이분 탐색 과정 전에 다음과 같은 배열을 정의함으로써 해결할 수 있다.

 

letter[i][j]: 첫 번째 문자에서 i번째 문자까지 알파벳 j의 출현 횟수

 

이를 통해 a번째 문자부터 b번째 문자까지의 연속되는 부분 문자열에서 알파벳 j의 출현 횟수를 구할 경우 letter[b][j] - letter[a - 1][j]를 계산하면 될 것이다. 이는 일종의 누적합으로 볼 수 있겠다.

 

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

const int N_MAX = 100000;

int n;
string s;

int letter[N_MAX + 1][26];

int main(){
    cin >> n >> s;
    
    int s_len = (int)s.length();
    
    for (int i = 1; i <= s_len; i++){
        for (int j = 0; j < 26; j++){
            letter[i][j] = letter[i - 1][j];
        }
        letter[i][(int)(s[i - 1] - 'a')] += 1;
    }
    
    int left = 1, right = s_len;
    
    int ans = 0;
    while(left <= right){
        int mid = left + (right - left) / 2;
        bool possible = false;
        for (int i = mid; i <= s_len; i++){
            // 해당 구간을 조건을 만족하여 읽을 수 있는지
            int cnt = 0;
            for (int j = 0; j < 26; j++){
                if (letter[i][j] > letter[i - mid][j]){
                    cnt += 1;
                }
            }
            if (cnt <= n){
                possible = true;
                break;
            }
        }
        if (possible){
            ans = mid;
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
    printf("%d\n", ans);
    
    return 0;
}

 

 

 

2. 두 포인터로 풀기

 

두 포인터(Two Pointer)를 사용하면 시간 복잡도가 O(N*logN)이 아니라 O(N) 안에 해결할 수 있다.

 

문자열의 왼쪽에서부터 오른쪽으로 탐색하면서 부분 문자열을 탐색하는데, 각 부분 문자열마다 몇 개의 서로 다른 종류의 알파벳이 사용되었는지 세는 방법이다. 그런데 현재 보고 있는 부분 문자열에 사용된 알파벳 종류 수가 N보다 크면 그 뒤에 이어지는 문자열도 인식이 불가능하므로 새로 보고자 하는 부분 문자열의 시작 위치를 다음 문자로 이동한다.

 

코드 구현을 위해 필요한 변수를 다음과 같이 정의했다.

 

cnt: left부터 i까지의 부분 문자열(S[left] ~ S[i])에서 사용된 알파벳 종류 수

letter[c]: left부터 i까지의 부분 문자열(S[left] ~ S[i])에서 알파벳 c가 사용된 횟수

 

우선 left와 i를 첫 번째 문자를 가리키도록 하고, cnt와 ans는 1로 초기화한다. 만약 cnt가 N 이하이면 i를 1만큼 증가시킨다. cnt가 N보다 크면 이후에 이어지는 문자열도 인식이 불가능하므로 left를 1만큼 증가시켜서 다음 문자부터 i까지의 부분 문자열을 본다. 주의할 점은 left 또는 i를 증가시킬 때 left와 i가 가리키는 문자에 따라 배열 letter의 원소값을 업데이트 해야 한다는 점이다. 위의 필기 노트에서 적은 예시를 참고하면 과정을 좀 더 쉽게 이해할 수 있을 것이다.

 

코드로 구현하면 다음과 같다.

 

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

const int N_MAX = 100000;

int n;
int letter[26];
char s[N_MAX + 1];

int main(){
    scanf("%d", &n);
    scanf("%s", s);
    
    int cnt = 1;
    int ans = 1;
    int left = 0;
    
    letter[s[0] - 'a'] += 1;
    
    for (int i = 1; s[i] != 0; i++){
        if (letter[s[i] - 'a'] == 0){
            cnt += 1;
        }
        letter[s[i] - 'a'] += 1;
        
        while(cnt > n){
            letter[s[left] - 'a'] -= 1;
            if (letter[s[left] - 'a'] == 0){
                cnt -= 1;
            }
            left += 1;
        }
        
        if (i - left + 1 > ans){
            ans = i - left + 1;
        }
    }
    printf("%d\n", ans);
    
    
    return 0;
}