문제
길이가 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의 길이가 될 때까지 추가하는데, 두 문자열의 차이가
가장 덜 나도록 하는 차이를 찾으면 된다.
나의 풀이를 요약하자면, B를 A로 잘랐을 때 A와 가장 차이가 적게 날 수 있는 배열을 찾았다.
그런 다음 해당 배열을 A와 비교하여 차이를 찾았다. 그게 전부다.
예를 들어, A는 "koder" 이고 B는 "topcoder" 라고 가정해보겠다.
결국 가장 적게 될 수 있는 방법은 A 앞에 "top"을 붙여서 "topkoder"을 만든 다음
B와 비교하면 1개 차이가 나게 된다.
이는 어떻게 보면, A에 앞 뒤에는 마음대로 원하는 문자열을 추가할 수 있기 때문에
무조건 B와 같은 것을 추가할 수 있게 된다.
따라서, koder을 B의 coder부분과 비교해 두 배열의 차이 1만 구하면 되는 것이다.
이 방식으로 구현해보았다.
코드
A,B = map(str,input().split())
lenA = len(A)
lenB = len(B)
answer = []
endidx = lenA - 1
startidx = 0
if lenA<lenB:
while endidx <= lenB - 1:
count = 0
new = str(B[startidx:endidx+1])
for i in range(lenA):
if new[i] != A[i]:
count += 1
answer.append(count)
endidx += 1
startidx += 1
else:
count = 0
for i in range(lenA):
if A[i] != B[i]:
count += 1
answer.append(count)
print(min(answer))A와 B 배열을 문자열로 받은 다음, 길이 변수까지 만든다.
다음으로 두 문자열의 길이를 비교한다.
1) 큰 if-else 중 if 부분의 의미
두 문자열의 길이가 다르면, B 길이가 될 떄까지 추가할 수 있다.
나는 B문자열에서 A문자열 크기만큼 slice한 다른 문자열을 만들었다.
따라서 slice에 필요한 처음 인덱스와 마지막 인덱스를 지정한다.
(참고로, slice 은 A[1:3] 이라면 A[1],A[2] 만 됨으로 마지막 범위애는 +1 만큼 더해줘야 한다.)
마지막 인덱스가 문자열 B 길이보다 1만큼 작을 떄까지 반복한다. (배열은 크기 -1까지가 최대)
그 다음, 문자열을 slice하여 새로운 문자열 new에 담는다.
new와 A는 길이가 똑같은 문자열이 되었기 때문에 두 문자열의 다른 개수를 세면 된다.
2) 큰 if-else 중 else 부분의 의미
두 문자열의 길이가 같으면 더 추가할 수 없다.
그렇기 떄문에 for문을 돌려 다른 부분의 개수를 세면 된다.
결론적으로, answer에 count되는 모든 값들을 담은 상태이다.
따라서 가장 최소의 값을 출력하면 된다.
💌
후기
처음에 이 로직을 짜고 모든 입출력 값이 맞길래 제출을 해보았다.
근데 채점 시작하자마자 틀렸다고 나오는 것이다.
그래서 온갖... 곳을 뒤지며 반례를 넣어봤는데 출력이 맞게 나오는 것이다 !!! ㅠㅠ
뭐지? 멘붕이 왔는데 알고보니 내가 구현 중에 확인을 위해 만들었던 print()을
안지웠던 것이 문제였다. 하하하 하하하 !!! 하하하 !!!
이 또한 재미있군
