[백준] 16472 - 고냥이

1. 문제

16472번: 고냥이

2. 개요

고양이말 번역기의 베타버전이 출시했다.

이 베타버전은 문제가 많아 주어진 문자열에서 최대 N종류의 알파벳을 가진 연속된 문자열만 인식할 수 있다.

한 문자열이 주어졌을 때, 번역기가 인식할 수 있는 부분 문자열의 최대 길이를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

투포인터와 Set을 이용한다.

포인터가 가리키는 문자를 각각 Set에 넣는다.

만약 Set의 길이가 N이하라면 r+1한다.

N이상이라면 r - l과 현재까지의 최대길이를 비교해 더 긴 값을 답으로 갱신하고, l을 1만큼 늘리고 r을 l+1로 초기화한다. 또한 Set을 초기화한다.

이를 r이 문자열의 길이를 초과할때까지 반복한다.

반복문을 탈출하고 마지막으로 현재까지의 최대길이와 r - l을 비교해 답을 갱신한 뒤, 답을 출력한다.

3-2. Python

import sys

alphaset = set()

N = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()

answer = 0
l, r = 0, 1

while l < r and r < len(S):
    alphaset.add(S[l])
    alphaset.add(S[r])

    if len(alphaset) <= N:
        r += 1

    else:
        answer = max(answer, r - l)
        l += 1
        r = l + 1
        alphaset.clear()

answer = max(answer, r - l)
print(answer)

3-3. C#

namespace boj_16472
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            string S = Console.ReadLine().TrimEnd();

            HashSet<char> alphaSet = new();

            int answer = 0, l = 0, r = 1;

            while (l < r && r < S.Length)
            {
                alphaSet.Add(S[l]);
                alphaSet.Add(S[r]);

                if (alphaSet.Count <= N)
                    r++;

                else
                {
                    answer = (int)MathF.Max(answer, r - l);
                    l++;
                    r = l + 1;
                    alphaSet.Clear();
                }
            }

            answer = answer = (int)MathF.Max(answer, r - l);
            Console.WriteLine(answer);
        }
    }
}