20437 문자열 게임 2 (C#) [Gold V]

 

양의 정수 K와 알파벳 소문자로 이루어진 문자열을 입력받을 때,

(조건 1) 어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이와

(조건 2) 어떤 문자를 정확히 K개를 포함하며 첫 번째와 마지막 문자가 같은 연속된 문자열의 길이를 구해주세요.

(구할 수 없다면 -1을 반환합니다.)

 

 

풀이 방법

1. 문제의 함정

조건 1과 조건 2는 탐색 방법이 다를 것 같지만 사실 그렇지 않습니다.

조건 2는 첫 번째와 마지막 문자가 같다는 차이점이 보이지만, 조건 1도 마찬가지입니다.

"aaa", "baa", "aba" 조건 1은 모든 경우에서 조건 2와 마찬가지로 첫 번째 문자와 마지막 문자가 같습니다.

 

2. 시간초과 해결법

문자열의 길이는 최대 1만, 문제의 수는 최대 100개 입니다.

즉, N * N의 속도로 해결하려면 시간초과가 발생합니다.

그렇기에 최대한 효율적으로 문제를 해결해야 하기에 문자의 수가 K개인 애들만 탐색을 진행하며 속도를 개선합니다.

또한, 문자의 수가 K개인 애들을 N * N번 순회하는 것이 아니라 N번만 순회할 수 있도록

같은 문자열들의 인덱스를 리스트에 보관하고 arr[i]의 인덱스번호와 arr[i + K -1]의 인덱스 번호의 거리를 찾는 방식으로 속도를 개선합니다.

 

 

3. Dictionary를 이용하다

Dictionary<char, List<int>> dic = new Dictionary<char, List<int>>();

for (int i = 0; i < str.Length; i++)
{
	char c = str[i];
	if (!dic.ContainsKey(c))
		dic.Add(c, new List<int>());

	dic[c].Add(i);
}

 

입력받은 문자열을 순회하며 같은 문자들의 인덱스를 Dictionary에 보관합니다.

이때, 순서대로 인덱스를 list에 넣기 때문에 dictionary에 있는 list는 자동으로 오름차순 정렬이 됩니다.

그럼, 어떤 문자가 정확히 K개 있는 문자열을 찾을 때, arr[i], arr[i + K - 1]가 존재한다면 두 인덱스 사이에는 무조건 K개의 같은 문자열이 있게됩니다

 

foreach (var tuple in dic.ToArray())
{
	if (tuple.Value.Count < K)
		dic.Remove(tuple.Key);
}

이후, 보관된 인덱스의 크기가 K보다 작다면 조건에 성립할 수 없기 때문에 제거합니다.

(제거하지 않고 continue를 해도 괜찮습니다만 이해를 위해 제거했습니다)

 

 

4. 최소 거리와 최대 거리 찾기

foreach (var tuple in dic)
{
    for (int i = 0; i < tuple.Value.Count; i++)
    {
        int j = i + (K - 1);
        if (j >= tuple.Value.Count) 
            continue;

        int s = tuple.Value[i];
        int e = tuple.Value[j];

        minLen = Math.Min(e - s + 1, minLen);
        maxLen = Math.Max(e - s + 1, maxLen);
    }
}

문자의 수가 K개 이상인 문자들을 담은 List들을 순회합니다.

arr[i]와 arr[i + k - 1]의 거리 (e - s + 1)을 구하고 최소 거리와 최대 거리를 찾아줍니다.

 

위 방식은 중복 문자의 수가 K개 이상인 문자열을 1번씩만 순회하기 때문에 굉장히 빠른 속도로 문제 해결이 가능합니다. 

 

 

 

정답 코드

Main 함수

class Program
{
    static void Main(string[] args)
    {
        Solution solution = new Solution();
        int N = int.Parse(Console.ReadLine());

        while (N-- > 0)
        {
            string str = Console.ReadLine();
            int K = int.Parse(Console.ReadLine());

            List<int> result = solution.solution(str, K);
            Console.WriteLine(string.Join(" ", result));  
        }
    }
}

 

 

solution 함수

public class Solution
{
    public List<int> solution(string str, int K)
    {
        Dictionary<char, List<int>> dic = new Dictionary<char, List<int>>();
        int minLen = int.MaxValue;
        int maxLen = int.MinValue;

        for (int i = 0; i < str.Length; i++)
        {
            char c = str[i];
            if (!dic.ContainsKey(c))
                dic.Add(c, new List<int>());

            dic[c].Add(i);
        }

        foreach (var tuple in dic)
        {
            if (tuple.Value.Count < K)
                continue;

            for (int i = 0; i < tuple.Value.Count; i++)
            {
                int j = i + (K - 1);
                if (j >= tuple.Value.Count) 
                    continue;

                int s = tuple.Value[i];
                int e = tuple.Value[j];

                minLen = Math.Min(e - s + 1, minLen);
                maxLen = Math.Max(e - s + 1, maxLen);

            }
        }

        if (minLen == int.MaxValue)
            return new List<int>() { -1 };
        else
            return new List<int>() { minLen, maxLen };
    }
}