[코딩테스트] [16472] 고냥이

[16472] 고냥이

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

1 초

512 MB

6343

2645

1896

40.085%

문제

고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고양이의 언어로, 고양이의 언어를 사람의 언어로 바꾸어 주는 희대의 발명품이 될 것이다.

현재 고양이말 번역기의 베타버전이 나왔다. 그러나 이 베타버전은 완전 엉망진창이다. 베타버전의 번역기는 문자열을 주면 그 중에서 최대 N개의 종류의 알파벳을 가진 연속된 문자열밖에 인식하지 못한다. 굉장히 별로지만 그나마 이게 최선이라고 사람들은 생각했다. 그리고 문자열이 주어졌을 때 이 번역기가 인식할 수 있는 최대 문자열의 길이는 얼마인지가 궁금해졌다.

고양이와 소통할 수 있도록 우리도 함께 노력해보자.

입력

첫째 줄에는 인식할 수 있는 알파벳의 종류의 최대 개수 N이 입력된다. (1 < N ≤ 26)

둘째 줄에는 문자열이 주어진다. (1 ≤ 문자열의 길이 ≤ 100,000) 단, 문자열에는 알파벳 소문자만이 포함된다.

출력

첫째 줄에 번역기가 인식할 수 있는 문자열의 최대길이를 출력한다.

문제풀이

이 문제는 소문자로 이루어진 문자열에서 N개 이하의 알파벳 종류만 사용되는 가장 긴 부분 문자열의 길이를 구하는 문제이다.

BruteForce 풀이 (완전탐색방법)

완전 탐색 방법으로 누적합을 이용하여 푸는 방법도 있다.

for (int i = 1; i <= L; i++)
	for (int j = i; j <= L; j++) {
		int count = 0;
		for (int alp = 0; alp < 26; alp++) 
			if (accAlp[j][alp] - accAlp[i - 1][alp] > 0)
				count++;
		if (count <= N) ans = Math.max(ans, j - i + 1);
	}

하지만 이런 코드는 O(N^2)가 발생하기에 시간초과가 발생할 것이다.

투 포인터 풀이

그렇다면 투 포인터를 사용해서 문제를 풀어보자.

int nextIndex = 0;
int[] alphabetFrequency = new int[26];
for (int i = 0; i < L; i++) {
	while (nextIndex < L) {
		alphabetFrequency[nyang[nextIndex++] - 'a']++;
		if(getAlphabetCount(alphabetFrequency) > N) {
			alphabetFrequency[nyang[--nextIndex] - 'a')--;
			break;
		}
	}
	ans = Math.max(ans, nextIndex - i);
	alphabetFrequency[nyang[i] - 'a']--;
}

static int getAlphabetCount[int[] alphabetFrequency) {
	int uniqueAlphabetCount = 0;
	for (int i = 0; i < alphabetFrequency.length; i++)
		if(alphabetFrequency[i] > 0)
			uniqueAlphabetCount++;
	return uniqueAlphabetCount;
}

getAlphabetCount 함수안 반복문 때문에 시간복잡도가 O(26*L)이 나온다.

조건을 확인할때마다 O(26)이다. 바뀌는 종류는 1글자인데 개선할 수 있을 것 같다.

1. 증가시킨 알파벳의 개수가 0에서 늘어났을 때
2. 감소시킨 알파벳의 개수가 0이 되었을 때

두 경우만 알파벳 종류가 변한다. 

매번 전체 알파벳을 확인하지 않고 해당 상황에만 관리해줄 수 있다.

for(int i =0; i<L; i++) {
	while (nextIndex < L) {
		increaseFrequency(nyang[nextIndex++]);
		if (alphabetCount > N) {
			decreaseFrequency(nyang[--nextIdnex]);
			break;
		}
	}
	ans = Math.max(ans, nextIndex - i);
	decreaseFrequency(nyang[i]);
}

// 증가시킨 알파벳의 개수가 0에서 늘어났을 때
static void increaseFrequency(char alp) {
	if (alphabetFrequency[alp - 'a']++ == 0)
		alphabetCount++;
}

// 감소시킨 알파벳의 개수가 0이 되었을 때
static void increaseFrequency(char alp) {
	if (--alphabetFrequency[alp - 'a']++ == 0)
		alphabetCount++;
}

전체코드

import java.util.Scanner;

class Main
{
    static int[] currentAlphabetFrequency = new int[26];
    static int currentUniqueAlphabetCount = 0;

    static void increaseFrequency(char alphabet) {
        if (currentAlphabetFrequency[alphabet - 'a']++ == 0)
            currentUniqueAlphabetCount++;
    }

    static void decreaseFrequency(char alphabet) {
        if (--currentAlphabetFrequency[alphabet - 'a'] == 0)
            currentUniqueAlphabetCount--;
    }

    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        char[] nyang = sc.next().toCharArray();
        int nextIndex = 0;
        int maxLength = 0;
        for (int i = 0; i < nyang.length; i++) {
            while (nextIndex < nyang.length) {
                increaseFrequency(nyang[nextIndex++]);
                if (currentUniqueAlphabetCount > N) {
                    decreaseFrequency(nyang[--nextIndex]);
                    break;
                }
            }
            maxLength = Math.max(maxLength, nextIndex - i);
            decreaseFrequency(nyang[i]);
        }
        System.out.println(maxLength);
    }
}

시간복잡도

이 알고리즘의 시간복잡도는 O(L)이다.