C# 1120 문자열

A="addabc", B="aababbc"일 때

A에 어떤 문자를 넣든 어차피 차이가 최소가 되도록 할 것이므로

B와 가장 비슷해지도록 만들 것이다

 

A[0]부터 A[5]를 B[0]부터 B[5]와 비교했을 때의 차이: 3

A[0]부터 A[5]를 B[1]부터 B[6]와 비교했을 때의 차이: 2

이렇게 모든 경우를 비교 했을 때 차이의 최솟값은 2가 나온다

 

마찬가지로 다른 예제들도 최솟값을 찾을 수 있다

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Study13
{
    class App
    {
        public App()
        {
            //BOJ 1120 문자열 
            //문제를 잘 읽고 푸세요 
            //https://www.acmicpc.net/problem/1120

            string[] arr = {
                "adaabc aababbc",
                "hello xello",
                "koder topcoder",
                "abc topabcoder",
                "giorgi igroig"
            };

            //여기부터 작성 하세요 

            for(int i = 0; i < arr.Length; i++)
            {
                string[] s = arr[i].Split(' ');
                int min = GetDifferenceMin(s[0], s[1]);

                Console.WriteLine(min);
            }
        }

        int GetDifferenceMin(string A, string B)
        {
            int min = A.Length;
            for (int i = 0; i < B.Length - A.Length + 1; i++)
            {
                int count = 0;
                for (int j = 0; j < A.Length; j++)
                {
                    if (A[j] != B[i + j])
                        count++;
                }
                min = Math.Min(count, min);
            }
            return min;
        }
    }
}

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