[백준1120번] 문자열

문제 링크 >> https://www.acmicpc.net/problem/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의 차이를 최소가 되도록 했을 때, 그 차이를 출력하시오.

 

 

📝 풀이

import sys

str1, str2 = sys.stdin.readline().split()
arr = []

for i in range(len(str2) - len(str1) + 1):
  count = 0
  for j in range(len(str1)):
    if str1[j] != str2[i+j]:
      count += 1
  arr.append(count)

print(min(arr))

 

이 문제는 좀 어려웠다.

문제에서 A와 B의 길이가 같아질 때까지 A의 앞이나 뒤에 아무 알파벳을 추가한다고 했는데 무슨 알파벳을 추가해야 정답이 될지 감이 잡히지 않았다.

 

결국 문제의 답은 A에 알파벳을 추가하는 게 아니라 B를 잘라가며 A와 비교하는 것이었다.

문제의 풀이는 다음과 같다.

 

문자열 A와 B의 길이를 비교하면 A가 B보다 작거나 같다.

따라서 두 문자열의 길이가 같을 때는 통째로 비교하면 되지만 길이가 다를 때는 A의 길이에 맞춰서 그만큼씩만 비교하면 되는 것이다.

 

근데 또 이 풀이를 그림으로 그리다보니 생각난 개념이 있었다.

바로 슬라이딩 윈도우다.

 

슬라이딩 윈도우는 리스트를 순회하며 연속적으로 같은 개수의 요소를 참조할 때 쓰면 유용한 알고리즘인데 이를 적용해도 좋을 것 같다는 생각이 들었다.

(슬라이딩 윈도우 참조는 여기에 >> https://cansweep.tistory.com/235)

 

import sys

str1, str2 = sys.stdin.readline().split()
arr = []

start = 0
for end in range(len(str1), len(str2)+1):
  temp = str2[start:end]
  count = 0
  for i in range(len(temp)):
    if str1[i] != temp[i]:
      count +=1
  arr.append(count)
  start+=1
  
print(min(arr))

 

첫 번째 for문에서 end는 자를 문자열의 끝 인덱스를 가리킨다.

따라서 start가 0부터 시작해 for문을 순회할 수록 start와 end가 모두 1씩 증가하며 창을 밀듯이 str2를 잘라나가는 것이다.

start와 end의 값에 따라 자른 문자열은 temp에 저장한 후 temp와 str1의 문자들을 비교해 문자 구성이 다른 경우의 수 중 최솟값을 출력한다.

 

 

 

슬라이딩 윈도우를 사용해서 문제를 푼 게 더 오래 걸리지 않을까 했는데 의외로 근소한 차이지만 시간이 단축되었다.