백준 #1120

문자열 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

13419

7052

6144

53.890%

문제

길이가 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의 차이를 최소로 하는 프로그램을 작성하시오.

입력

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

출력

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

예제 입력 1 복사

adaabc aababbc

예제 출력 1 복사

2

예제 입력 2 복사

hello xello

예제 출력 2 복사

1

예제 입력 3 복사

koder topcoder

예제 출력 3 복사

1

예제 입력 4 복사

abc topabcoder

예제 출력 4 복사

0

예제 입력 5 복사

giorgi igroig

예제 출력 5 복사

6

출처

• 문제를 번역한 사람: baekjoon
• 문제의 오타를 찾은 사람: chsun0303
• 빠진 조건을 찾은 사람: jh05013, purpose

알고리즘 분류

• 구현
• 문자열
• 브루트포스 알고리즘

 

 

 

 

 

 

---

import sys

if __name__ == '__main__':

    A, B = sys.stdin.readline().split()

    n = len(B) - len(A)
    cnt = [0 for _ in range(n+1)]

    # 처음에는 모두 앞에 추가한다고 가정하고 하나씩 뒤로 넘기면서 진행
    for i in range(n+1):
        for j in range(i, len(B) - (n-i)):
            if A[j-i] != B[j]:
                cnt[i] += 1

    print(min(cnt))

풀긴 풀었는데 왜 이렇게 머리가 안돌아가는지 모르겠다. 풀이 방법은 추가한 문자들은 항상 A와 B가 같을 것이므로 예를 들어 A의 문자 길이가 4이고 B의 문자 길이가 7일 때 A는 4개의 문자만 생각하면 된다. 문자를 추가하는 방법은 아래 4가지이므로 4가지 중 가장 작은 값을 출력하면 된다.

 

0 A 3

1 A 2

2 A 1

3 A 0