백준#1120 - 문자열

https://www.acmicpc.net/problem/1120

1120번: 문자열

그리디 알고리즘으로 분류된 문자열 문제 입니다.

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace _1120
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] splitInput = Console.ReadLine().Split(' ');
            string A = splitInput[0];
            string B = splitInput[1];
 
            Program p = new Program();
            int diff = B.Length;
 
            for(int i = 0; i < B.Length - A.Length + 1; i++)
            {
                if (p.GetStringDiff(A, B.Substring(i, A.Length)) < diff)
                    diff = p.GetStringDiff(A, B.Substring(i, A.Length));
            }
 
            Console.WriteLine(diff);
        }
 
        public int GetStringDiff(string a, string b)
        {
            int count = 0;
            for(int i = 0; i < a.Length; i++)
            {
                if (a[i] != b[i])
                    count++;
            }
            return count;
        }
    }
}
 

처음 볼것은 GetStringDIff입니다. string A와 Substring B를 비교할 것인데 둘의 각 문자를 보고

다르다면 카운트를 하나씩 늘려 차이를 반환받습니다.

 

다음 main에서 길이를 비교합니다. 비교의 차이 + 1 만큼 반복합니다.

a의 길이가 3이고 b의 길이가 5라면 B.Substring(0, 3)부터 B.Substring(2, 5)까지 차례대로 가져와

그 GetStringDiff를 구합니다. 그 중 가장 작은것을 가지고 있다가 출력 했습니다.

 

A의 길이가 B보다 작은 경우 이를 고려하지 않아도 됩니다.

ex) A : abc, B : aabcd일 경우 => B의 a abc d 처럼 B의 Substring중 차이가 가장 작은 부분을 반환

받을 것이며 A에 추가하는 것은 당연히 B와 같아지도록 앞의 a, 마지막에 d를 추가할 것입니다. A가

B의 Substring중 그 차이가 가장 작은 부분을 찾을 수 있다면 나머지 길이를 맞추는 과정은 추가하는

모든 문자가 B와 같아지도록 한다는 것을 알 수 있습니다.