[C#] 백준 11478번 서로 다른 부분 문자열의 개수

[ 문제 ]

문자열 S가 주어졌을 때, S의 서로 다른 부분 문자열의 개수를 구하는 프로그램을 작성하시오.

부분 문자열은 S에서 연속된 일부분을 말하며, 길이가 1보다 크거나 같아야 한다.

예를 들어, ababc의 부분 문자열은 a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc가 있고, 서로 다른것의 개수는 12개이다.

 

[ 코드 ]

1. 내 코드

StreamReader sr = new (new BufferedStream(Console.OpenStandardInput()));
StreamWriter sw = new (new BufferedStream(Console.OpenStandardOutput()));

string S = sr.ReadLine();
HashSet<string> A = new HashSet<string>();
int count = S.Length;

for (int i = 0; i < S.Length; i++)
{
    for (int j = 1; j <= count; j++)
    {
        A.Add(S.Substring(i, j));
    }
    count--;
}

sw.Write(A.Count);
sw.Flush();
sw.Close();
sr.Close();

 

2. 다른 사람 코드

- Substring 직접 구현

using System;
using System.Collections.Generic;

public class Program
{
    public static void Main(string[] args)
    {
        string str = Console.ReadLine();
        HashSet<string> setOfSubstrs = new HashSet<string>();

        int ans = 0;
        int strLen = str.Length;
        for (var i = 1; i <= strLen; i++)
        {
            foreach (var subStr in str.GetSubStrs(i))
            {
                setOfSubstrs.Add(subStr);
            }
            ans += setOfSubstrs.Count;
            setOfSubstrs.Clear();
        }

        Console.WriteLine(ans.ToString());
    }
}

public static class StringExtensions
{
    public static IEnumerable<string> GetSubStrs(this string str, int len)
    {
        char[] chars = str.ToCharArray();
        for (var i = 0; i < chars.Length; i++)
        {
            int startIndex = i;
            int endIndex = i + len;
            if (endIndex > chars.Length) break;
            char[] subChars = new char[len];
            for (var j = startIndex; j < endIndex; j++)
            {
                subChars[j - i] = chars[j];
            }
            yield return new string(subChars);
        }
    }
}

 

[ 추가 ]

두번째 코드를 보면서 처음보는 return이 눈에 띄어 검색해보았다.

 

yield return:

 

return은 메서드를 즉시 종료하고 한번에 호출자에게 반환하는 반면,

yield return은 한번 만날때마다 호출자에게 반환된다.

이때 호출자가 이어져서 실행되는게 아니라 다시 yield return로 돌아와 기존의 메서드를 실행한다.

대용량 데이터를 효율적으로 처리할 수 있어서 시간과 메모리 사용량을 줄일 수 있다고 한다.

(But 순차적인 데이터 일때... 비순차적인 데이터면 좋지않을 수도있다.)

 

<참고 블로그>

https://velog.io/@youhyeoneee/C-yield

[C#] yield

 

[ 실행화면 ]

case: 1

 

 

 

 

 

---

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

11478번: 서로 다른 부분 문자열의 개수