[백준/파이썬] 1120번 문자열 풀이
업데이트:
문제 정보
- 문제 출처: 백준 온라인 저지
- 문제 링크: 1120번 문자열
- 문제풀이 코드 GitHub 링크
- 제출 언어: Python 3
풀이
문제
길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다.
두 문자열 A와 B가 주어진다. 이때, A의 길이는 B의 길이보다 작거나 같다. 이제 A의 길이가 B의 길이와 같아질 때 까지 다음과 같은 연산을 할 수 있다.
- A의 앞에 아무 알파벳이나 추가한다.
- A의 뒤에 아무 알파벳이나 추가한다.
이때, A와 B의 길이가 같으면서, A와 B의 차이를 최소로 하는 프로그램을 작성하시오.
(A와 B의 길이는 최대 50이고, A의 길이는 B의 길이보다 작거나 같고, 알파벳 소문자로만 이루어져 있다.)
코드
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))
설명
쉽습니다. 브루트 포스로 풀 수 있습니다.
브루트 포스란, 단순무식하게 가능한 경우를 하나하나 대입해보는걸 뜻합니다.
어렸을 때 사물함에 3자리 혹은 4자리 자물쇠를 한번쯤 써보셨을 텐데, 비밀번호를 까먹어서 하나하나 다 돌려보고 있는 상황을 떠올리시면 정확합니다.
a의 각 자리가 b에서 i만큼 bias를 두고 비교했을 때 다른 문자의 수를 배열에 저장, 최종적으로 배열의 값 중 최소값을 출력하면 됩니다.
b가 a문자열보다 더 길어서 남는 공간은 아무거나 넣을 수 있으므로 같은 문자가 있다고 가정, 비교하지 않습니다.
예제
입력
adaabc aababbc
실행 과정
1.
| a | a | b | a | b | b | c |
| a | d | a | a | b | c | |
| 0 | 1 | 1 | 0 | 0 | 1 | 0 |
3점
2.
| a | a | b | a | b | b | c |
| a | d | a | a | b | c | |
| 0 | 0 | 1 | 0 | 1 | 0 | 0 |
2점
점수 리스트 : [3, 2]
답
2
댓글남기기