[BOJ][Python]1120번 풀이

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

1120번: 문자열

a,b = input().split()
ans = 50
for i in range(len(b)-len(a)+1):
    tmp = 0
    for j in range(len(a)):
        if a[j] != b[i+j]:
            tmp += 1
    if tmp < ans:
        ans = tmp
print(ans)

크게 어려운 문제는 아니지만 구현 문제 특성상 길을 잘못 잡으면 시간 지체가 많이 된다는 점에서 풀어보면 좋은 문제라고 생각합니다.

 

문제 접근은 a와 b가 아무리 길이 차이가 많이 나든 상관없이 a와 b를 한글자씩 비교하면서 가장 다른 글자가 작게 나오는 경우를 찾으면 된다는 것입니다(문제 조건에서 길이를 맞출 때는 해당 위치에서 앞 뒤로 알파벳을 붙일 수 있고, b와 같은걸 붙이면 최소 갯수가 변하지 않기 때문에 어떤 경우든 최소 갯수를 늘리지 않는 알파벳을 추가한다고 가정). 무슨 알파벳을 갖다 붙이든 특정 경우의 갯수 차이가 최소라면 해당 값이 답이 되기 때문입니다. 따라서 a와 b의 글자를 비교하기 위한 반복문을 구성하고 b의 시작 위치를 변경하면서 글자 차이를 tmp에 저장합니다. 그리고 기존의 ans가 tmp보다 크다면 tmp를 ans 자리에 넣어서 최종적으로는 최솟값이 ans에 저장되어 있도록 코드를 구성합니다.

 

구현 문제 특성상 문제 푸는 사람을 헷갈리게 하고 엉뚱한 곳에 붙잡혀서 시간을 쏟도록 하는 경우가 종종 있습니다. 저도 아직 완전히 해당 함정들을 극복했다고는 말할 수 없지만 분명 이렇게 하나씩 풀어나가다 보면 웰노운은 아무렇지 않게 풀 수 있는 날이 오겠죠.