[백준 - C#] 1120번 문자열

문제링크

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

1120번: 문자열

 

문제

길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다.
예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다.

두 문자열 A와 B가 주어진다. 이때, A의 길이는 B의 길이보다 작거나 같다.
이제 A의 길이가 B의 길이와 같아질 때 까지 다음과 같은 연산을 할 수 있다.

1. A의 앞에 아무 알파벳이나 추가한다.
2. A의 뒤에 아무 알파벳이나 추가한다.

이때, A와 B의 길이가 같으면서, A와 B의 차이를 최소로 하는 프로그램을 작성하시오.

조건

시간제한 : 2초
메모리 제한 : 128 MB

입력

첫째 줄에 A와 B가 주어진다.
A와 B의 길이는 최대 50이고, A의 길이는 B의 길이보다 작거나 같고, 알파벳 소문자로만 이루어져 있다.

출력

A와 B의 길이가 같으면서, A와 B의 차이를 최소가 되도록 했을 때, 그 차이를 출력하시오.

 

문제정리

1. 두 문자열의 차이는 X[i] != Y[i] 일 때 개수입니다.
2. 문자열의 길이는 A <= B 이다.
3. 문자열의 길이가 같을 때까지 A문자열에 문자를 붙입니다.
4. A와 B의 길이가 같으면서 차이를 최소로 하는 개수를 구하라.

이번 문제의 경우 A와 B의 문자열의 길이를 똑같이 맞추면서 각 자릿수마다 문자가 다른 갯수의 최솟값을 구하는 문제입니다.

결국 A에 문자열을 붙일때는 무조건 같게 붙이면 되기 때문에 A와 B를 비교하여 가장 많이 같았을 때의 갯수를 구하면 그것이 최솟값입니다.

 

예를들어 예제 4번의 경우 A : abc / B : topabcoder 의 경우 abc가 B안에 겹치는 부분이 있기 때문에 나머지 자릿수는 똑같게 채우기만 하면 정답은 0 입니다.

 

C# 코드

static void Main(string[] args)
{
    //  https://bokhead.tistory.com/
    StreamWriter writer = new StreamWriter(Console.OpenStandardOutput());
    StreamReader reader = new StreamReader(Console.OpenStandardInput());
 
    string[] input = reader.ReadLine().Split();
    int min = 50;
 
    // A문자열과 B문자열의 차이만큼 반복문 진행
    for (int i = 0; i <= input[1].Length - input[0].Length; i++)
    {
        int count = 0;
 
        for (int j = 0; j < input[0].Length; j++)
        {
            // 해당 문자가 같으면 카운팅 증가
            if (input[0][j] != input[1][j + i])
                count++;
        }
 
        min = (min > count) ? count : min;
    }
 
    writer.WriteLine(min);
 
    writer.Close();
    reader.Close();
}

 

읽어주셔서 감사합니다 오늘도 즐거운 하루 되세요.