[BOJ] 1120: 문자열

이슬비·2023년 2월 3일

Algorithm

목록 보기

70/110

사실 이게 왜 브루트포스에 있는지 아직 조금 아리까리

1. 내 풀이

a, b = map(str, input().split())
if len(a) != len(b):
    if a in b:
        a = b
    elif a[-1] == b[-1]:
        a = b[:len(b)-len(a)] + a
    elif a[0] == b[0]:
        a = a + b[len(a):]
    else:
        for i in range(len(a)):
            if a[i] in b:
                a = b[:b.index(a[i])]+a+b[len(b)-len(a):]
                break

count = 0
for i in range(len(a)):
    if b[i] != a[i]:
        count += 1
        
print(count)

제시된 테스트 케이스는 모두 맞은 코드였다. 결론은 틀림 ^^
Index Error도 떴었고, ~~... 나 혼자 여러 케이스를 생각하다가 그 케이스에만 맞는 그런 Overfitting이 일어나버린 그런 코드다.

2-1. 다른 풀이 1

a, b = input().split()
minCnt = 51

for i in range(len(b) - len(a) + 1):
    count = 0
    for j in range(len(a)):
        if b[j+i] != a[j]:
            count += 1
    if count < minCnt:
        minCnt = count
        
print(minCnt)

풀이 출처: https://wiselog.tistory.com/83

해당 코드 작성자님에 따르면,

문자열의 앞뒤에 어떤 문자를 삽입하든 상관이 없으니, b의 어느 위치에 a가 위치해야 가장 일치하는지만을 보이면 된다.

b의 인덱스 0부터 a를 비교하여 다른 문자의 개수를 찾고, a를 한 칸씩 옆으로 밀면서 최소값을 찾아간다.

라고 한다. 첫 번째 문장이 바로

for i in range(len(b) - len(a) + 1):

여기에 해당하는 듯하다. len(b)와 len(a)의 차이를 구함으로써, a라는 문자열을 b에 어디에 놓을지를 정하는 것이다. 그리고 a의 길이 중 남는 부분은 a를 넘어서는 그 b의 알파벳으로 채워넣으면 되는 것이다.

그리고 두 번째 문장은,

    count = 0
    for j in range(len(a)):
        if b[j+i] != a[j]:
            count += 1
    if count < minCnt:
        minCnt = count

여기에 해당한다. 하나씩 살펴보자. 테스트 케이스를 adaabc와 aababbc로 정했을 때,

첫 번째 for문의 범위는 2가 되고, 이 말은 a를

adaabc
aababbc

이런 식으로 놓겠다는 것이다. 자 그럼 그 다음 코드에 의해서 count가 0으로 초기화 되고 a의 길이가 범위로 주어지는 for문으로 입장하게 된다.

여기서 b의 인덱스와 a의 인덱스가 같지 않으면 count를 1을 높여주게 되는데, b[j+i] 인 이유는 첫 번째 for문에 의해 a와 비교해야 하는 index가 달라질 수 있기 때문이다. 그래서 a가 b에서 시작하는 index라고 볼 수 있는 i를 꼭 더해주어야 한다.

그렇게 a와 b의 비교를 끝마친 후에는 minCnt와 비교를 해주게 되는데, 이는 a와 b의 길이가 최대 50이므로, 출력으로 나올 수 있는 값은 50이기 때문에 초기값을 51로 지정해준다.

만약 count, 즉 현재 a의 위치에 따른 출력값이 minCnt보다 작게 되면 이를 minCnt로 설정해준다.

2-2. 다른 풀이 2

a, b = input().split()
b = list(b)
len_a = len(a)
max_cnt = 0
while len_a <= len(b):
    cnt = 0
    for i in range(len_a):
        if a[i] == b[i]:
            cnt += 1
    max_cnt = max(max_cnt, cnt)
    del b[0]
print(len_a - max_cnt)