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

목차

---

백준 단계별로 풀어보기

25.11.04

14단계: 집합과 맵

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

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

 

문제 풀이

: 서로 다른 부분 문자열의 개수를 구하는 것이므로 중복이 없어야 한다. 따라서 HashSet 자료구조에 모든 부분 문자열을 담고 HashSet의 크기를 출력하면 된다.

1. StreamReader로 입력값을 받아 문자열을 담을 변수 input 에 담고, 부분 문자열을 담을 HashSet인 hash 를 초기화한다.
2. 이중 for문을 통해 부분 문자열을 구하고 hash 에 추가한다.
   •     i 는 시작 index, j 는 끝 index이다.
   •     임시 문자열 temp 를 시작 index가 바뀔 때마다 초기화한다.
   •     끝 index가 증가할 때마다 temp 에 문자열을 누적시키면서 hash 에 추가한다.
3. StreamWriter로 hash 의 크기를 출력한다.

 

정답 코드

using System.IO;

class Backjoon
{
    static void Main(string[] args)
    {
        using var sr = new StreamReader(Console.OpenStandardInput());
        using var sw = new StreamWriter(Console.OpenStandardOutput());

        string input = sr.ReadLine();
        HashSet<string> hash = new HashSet<string>();

        for (int i = 0; i < input.Length; i++)
        {
            string temp = "";
            
            for (int j = i; j < input.Length; j++)
            {
                temp += input[j];
                hash.Add(temp);
            }
        }
        
        sw.Write(hash.Count);
    }
}