[백준] 1593 - 문자 해독

1. 문제

1593번: 문자 해독

2. 개요

마야 문자를 해독하려고 한다.

마야 문자로 쓰여진 단어는 문자의 순서가 제멋대로 섞여있다.

찾고자 하는 단어와 어떤 문자열이 주어졌을 때, 해당 문자열 내에 찾고자 하는 단어가 있을 수 있는 모든 경우의 수를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

먼저 알파벳 대소문자 52개의 갯수를 셀 딕셔너리를 만든다.

찾고자 하는 단어에서 각각의 문자의 수를 세어 딕셔너리를 갱신한다.

주어진 문자열에서 앞에서부터 찾고자 하는 단어의 길이만큼의 문자열을 떼어내 문자를 탐색하며 딕셔너리에서 해당 값을 1만큼씩 빼준다.

만약 찾고자 하는 단어와 동일한 단어일 가능성이 있다면 딕셔너리의 모든 값이 0이 되게 된다.

딕셔너리의 값들의 집합의 원소가 0 하나라면 이를 만족하므로 답을 1늘려준다.

이후 주어진 문자열의 찾고자 하는 단어의 길이 +1 인덱스부터 끝까지 탐색을 개시한다.

떼어냈던 문자열의 맨 앞을 버리며 딕셔너리의 값을 1늘려주고, 해당 인덱스의 문자를 떼어낸 문자열의 맨 뒤에 붙여나가며 딕셔너리의 값을 1만큼 빼내주며 딕셔너리의 값들의 집합을 확인한다.

탐색을 완료했다면 답을 출력한다.

3-2. Python

import sys
from collections import deque

g, s = map(int, sys.stdin.readline().split())

W = sys.stdin.readline().rstrip()
S = sys.stdin.readline().rstrip()

answer = 0
chardict = {}

for i in range(26):
    chardict[chr(ord('A') + i)] = 0
    chardict[chr(ord('a') + i)] = 0

for w in W:
    chardict[w] += 1

subword = deque(S[:g])

for sw in subword:
    chardict[sw] -= 1

if set(chardict.values()) == set([0]):
    answer += 1

for i in range(g, s):
    chardict[subword.popleft()] += 1
    chardict[S[i]] -= 1

    subword.append(S[i])

    if set(chardict.values()) == set([0]):
        answer += 1

print(answer)

3-3. C#

namespace boj_1593
{
    internal class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            string[] input = sr.ReadLine().Split();

            int g = int.Parse(input[0]);
            int s = int.Parse(input[1]);

            string W = sr.ReadLine().TrimEnd();
            string S = sr.ReadLine().TrimEnd();

            int answer = 0;
            Dictionary<char, int> worddict = new();

            for (int i = 0; i < 26; i++)
            {
                worddict[(char)('A' + i)] = 0;
                worddict[(char)('a' + i)] = 0;
            }

            foreach (char w in W)
                worddict[w] += 1;

            Queue<char> subword = new(S[..g]);

            foreach (char sub in subword)
                worddict[sub] -= 1;

            HashSet<int> resultset = worddict.Values.ToHashSet();

            if (resultset.Count == 1 && resultset.Contains(0))
                answer += 1;

            for (int i = g; i < s; i++)
            {
                worddict[subword.Dequeue()] += 1;
                worddict[S[i]] -= 1;

                subword.Enqueue(S[i]);

                resultset = worddict.Values.ToHashSet();

                if (resultset.Count == 1 && resultset.Contains(0))
                    answer += 1;
            }

            sw.WriteLine(answer);
            sw.Close();
        }
    }
}