백준 - 16472 고냥이 [투포인터]

 

16472번: 고냥이

 

1. 문제 요약

n과 문자열이 주어지고,

문자열에서 최대 n개의 종류의 알파벳을 포함한 문자열의 길이를 구하라.

 

2. 접근 방법

• 투포인터 알고리즘을 사용하여 문자열을 순차적으로 검사합니다.
• j(끝) 위치의 알파벳이 새로운 알파벳일 경우 count += 1을 하고 사용 중인 알파벳으로 표시합니다.
• 사용 중인 알파벳의 종류가 n보다 클 경우 줄어들 때까지 i(시작) 위치의 알파벳을 이동합니다.
  • 사용 중인 알파벳 종류가 하나 줄어들 경우 count -= 1 표시를 해줍니다.
• 현재 answer 값과 생성한 문자열의 길이(j-i)를 비교하여 큰 값을 취합니다.

 

3. 파이썬

def solution(n:int, arr:str):
    alphbet = [0] * 26

    answer, count, i, j = 0, 0, 0, 0
    while j < len(arr):
        if alphbet[ord(arr[j])-97] == 0:
            count += 1
        alphbet[ord(arr[j])-97] += 1

        while count > n and i < j:
            alphbet[ord(arr[i])-97] -= 1
            if alphbet[ord(arr[i])-97] == 0:
                count -= 1
            i += 1

        j += 1
        answer = max(answer, j-i)

    return answer

 

4. 자바

private static int solution(int n, char[] arr) {
    int[] alphabet = new int[26];
    int answer = 0;
    int count = 0;
    int i = 0;
    int j = 0;
    while (j < arr.length) {
        if (alphabet[arr[j] - 'a'] == 0) { // 새로운 알파벳일 경우
            count += 1;
        }
        alphabet[arr[j] - 'a'] += 1;

        while (count > n && i < j) { // count가 n보다 클경우 줄어들때까지 i위치를 이동
            alphabet[arr[i] - 'a'] -= 1;
            if (alphabet[arr[i] - 'a'] == 0) { // 사용중인 알파벳 하나를 없앴을 경우
                count -= 1;
            }
            i += 1;
        }

        j += 1;
        answer = Math.max(answer, j - i);
    }

    return answer;
}

 

5. 전체 코드

https://github.com/Ksiyeong/Algorithm/tree/main/%EB%B0%B1%EC%A4%80/Gold/16472.%E2%80%85%EA%B3%A0%EB%83%A5%EC%9D%B4