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

입력

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

출력

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

예제 입력 1

adaabc aababbc

예제 출력 1

2

 

 

👨‍🦲 나의 풀이

 

A, B=input().split()
length=len(B)-len(A)
ans=50

for i in range(length+1) :
    cnt = 0
    for j in range(len(A)) :
        if A[j] != B[i+j] :
            cnt+=1
    ans=min(ans, cnt)

print(ans)

 

B에서 문자열 A의 최적의 시작 위치를 찾는다. 빈 공간은 B랑 똑같이 채우면 되는 것이고.

예제를 아래에 나타냈다.

a	d	a	a	b	c
a	a	b	a	b	b	c

3개 차이난다.

 

	a	d	a	a	b	c
a	a	b	a	b	b	c

2개 차이난다. [1]인덱스에서 시작해야 A와 B의 차이가 최소가 된다.

 

 

👉 다른 사람 풀이

 

# https://neomindstd.github.io/%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4/boj1120/
a,b=input().split()

cnts=list()
for i in range(len(b)-len(a)+1) :
    cnt=0
    for j in range(len(a)) :
        if(a[j] != b[j+i]) :
            cnt+=1
    cnts.append(cnt)
print(min(cnts))

 

같은 알고리즘이다.

리스트 cnts에 값을 담고 min으로 가장 작은 값을 출력한다.

 

 

x, y=input().split()
minimum=50

for i in range(len(y)-len(x)+1) :
    temp=0
    for j in range(len(x)) :
        if x[j] != y[i+j] :
            temp+=1
    if temp < minimum :
        minimum=temp

print(minimum)

 

결과값을 구하는 과정만 살짝 다르고 이것도 같은 알고리즘이다.

유일하게 min함수 안 쓰고 비교 연산을 사용했다.

 

 

문제 출처 💁‍♀️ 백준