[백준] 1972 - 놀라운 문자

1. 문제

1972번: 놀라운 문자열

2. 개요

문자열에서 D만큼 거리가 떨어져있는 두 문자의 조합을 D쌍이라고 한다.

한 문자열의 D쌍들이 모두 다르다면, 이 문자열은 D유일하다고 한다.

또한 한 문자열의 모든 D에 대해 모든 D쌍들이 D유일하다면 이 문자열을 놀라운 문자열이라고 한다.

한 문자열이 주어졌을 때, 이 문자열이 놀라운 문자열인지 아닌지를 판별하는 문제.

3. 풀이 및 코드

3-1. 풀이

N길이의 문자열 S의 0쌍부터 N-2까지 탐색하면서 집합을 만들어 D유일한지 아닌지를 판별한다.

어떤 k에 대해 S의 k쌍의 집합의 개수가 N길이의 k쌍의 최대 개수와 같지 않다면 이는 중복이 있다는 얘기이고 D유일하지 않게 되어 놀라운 문자열이 아니게 된다.

이를 모든 D쌍에 적용하여 모든 D쌍이 유일한지 아닌지를 판단하여 알맞은 답을 출력한다.

3-2. Python

import sys

while True:
    S = sys.stdin.readline().rstrip()

    if S == '*':
        break

    dpair = set()
    result = 0

    for i in range(1, len(S)):
        dpair.clear()
        for j in range(len(S) - i):
            pair = S[j] + S[j + i]
            dpair.add(pair)

        if len(dpair) != len(S) - i:
            print("%s is NOT surprising." %S)
            result = 0
            break

        else:
            result += 1

    if result == len(S) - 1:
        print("%s is surprising." %S)

3-3. C#

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

            while (true)
            {
                string S = sr.ReadLine().TrimEnd();

                if (S == "*")
                {
                    sw.Close();
                    break;
                }

                HashSet<string> dpair = new();
                int result = 0;

                for (int i = 1; i < S.Length; i++)
                {
                    dpair.Clear();

                    for (int j = 0; j < S.Length - i; j++)
                    {
                        string pair = S[j].ToString() + S[j + i].ToString();
                        dpair.Add(pair);
                    }

                    if (dpair.Count() != S.Length - i)
                    {
                        sw.WriteLine($"{S} is NOT surprising.");
                        result = 0;
                        break;
                    }

                    else
                        result++;
                }

                if (result == S.Length - 1)
                    sw.WriteLine($"{S} is surprising.");

            }
        }
    }
}