[BOJ/C#] 16472 고냥이

문제

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

해석

알파벳 종류의 개수와 문자열이 주어졌을 때, 알파벳을 정하여 연속된 문자열의 최대 길이를 구하는 문제이다.
이는 문자열의 시작부분부터 마지막 부분까지 주어진 모든 구간에서 연속되는 값에 대해 순차적으로 비교해야한다. 따라서 투 포인터 알고리즘을 응용하여 문제를 해결할 수 있다는 것을 알 수 있다.

문제풀이

가장 중요하다고 생각한건 두 개의 포인터(시작, 끝) 사이에 알파벳의 종류가 몇 개가 포함됬는지 어떻게 구할 것인지라고 생각했다. 또한 알파벳이 섞여있을 경우 다른 종류를 추가하고 이전의 것을 제거하고 싶을 때 시작 포인터를 어디까지 옮겨야 하는지를 구하는 것이 중요했다.

예를들어 "acacaaabababbb"일 때 2가지의 종류만 사용 할 수 있다면 처음에는 a와 c만을 이용해서 길이를 구하다가 c를 버리고 b를 추가하고 싶을 때 c를 어디까지 버려야하는지를 고민할 것이다.

고민 끝에 Dictionary를 사용하기로 했다. key를 알파벳으로 value는 포인터 사이에 포함된 알파벳의 각각의 수를 저장한다.

반복문을 돌면서 최대로 저장할 수 있는 알파벳을 저장하고 그 때의 두 개의 포인터 사이의 알파벳의 갯수를 result 변수에 저장하면서 새로운 알파벳을 추가할 때는 제일 앞에 알파벳을 없애는 과정을 통해 답을 구할 수 있다.

코드

using System;
using System.Collections.Generic;
using System.Linq;

namespace Baekjoon
{
    internal class boj16472
    {
        static void plusChar(Dictionary<char, int> map, char c)
        {
            if (map.ContainsKey(c))
                map[c] += 1;
            else map[c] = 1;

            return;
        }

        static void minusChar(Dictionary<char, int> map, char c)
        {
            map[c] -= 1;
            if (map[c] <= 0)
                map.Remove(c);

            return;
        }

        static void solution()
        {
            Dictionary<char, int> map = new Dictionary<char, int>();
            int N = int.Parse(Console.ReadLine());
            String text = Console.ReadLine();
            int start = 0, end = 0, result = 0;

            while (end < text.Length)
            {
                while (map.Count <= N && end < text.Length)
                {
                    plusChar(map, text[end]);
                    end++;
                }
                result = Math.Max(result, end - 1 - start);

                while (map.Count > N)
                {
                    minusChar(map, text[start]);
                    start++;
                }
            }
            if (map.ContainsKey(text.Last()))
                result = Math.Max(result, end - start);
            else result = Math.Max(result, end - 1 - start);

            Console.WriteLine(result);
        }
        static void Main(string[] args)
        {
            solution();
            Console.ReadKey();
        }
    }

}