[실버 IV] 1120번. 문자열

 문제 

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

1120번: 문자열

 사용 언어 

Python3

 풀이 과정 

한번에 뜬 맞았습니다!!

처음에 로직을 짤 때 문자를 추가하는 함수까지 만들려고 했는데 생각해보니

문자를 추가한다면 비교 대상의 같은 위치와 같은 문자를 추가할 것이므로 실제로 문자를 추가할 필요는 없고 현재 A 덩어리가 B와 가장 많이 겹치는 부분의 차이를 찾으면 된다는 사실을 깨달았다. 이게 이 문제의 포인트였던 것 같다. 모든 문제에 이렇게 지름길(?) 로직을 찾을 수 있으면 얼마나 좋아~!

 제출 답안 

import sys

def compare(x, y):
  count = 0
  for i in range(len(x)):
    if x[i] != y[i]: # 각 위치의 문자 비교
      count += 1
  return count

def minimizeDiff(x, y):
  result = []
  count = 0
  times = len(y)-len(x)+1 # 인덱스 옮기며 비교할 횟수
  for i in range(times):
    result.append(compare(x, y[i:i+len(x)])) # y를 x길이만큼 슬라이싱하여 비교
  return min(result) # 그 중에 최솟값 반환

A, B = sys.stdin.readline().strip().split(' ')
if len(A) == len(B):
  print(compare(A, B))
else:
  print(minimizeDiff(A, B))

 공부한 내용 

문자열 비교

다른 언어의 strcmp와 같은 문자열 비교 내장 함수가 있나 찾아봤지만 없는 것 같고 대신 새롭게 안 내장 함수는 있었다.

두 문자열을 비교하는 데에는 다음과 같은 4가지 종류가 있다. 예제는 출처를 참고한다.

 

완전 일치 : ==, !=

문자열이 완전하게 일치하는지 비교하는 데에는 ==과 !=이 사용된다. ==는 두 문자열이 완전히 일치하면 True, 일치하지 않으면 False를 반환한다.!=는 두 문자열이 일치하지 않으면 True, 완전히 일치하면 False를 반환한다.

 

부분 일치 : in, not in
문자열이 부분적으로 일치하는지 비교하는 데에는 in과 not in이 사용된다. in은 어떤 문자열이 다른 문자열에 부분적으로 존재하면 True, 존재하지 않으면 False를 반환한다. not in은 어떤 문자열이 다른 문자열에 존재하지 않으면 True, 부분적으로 존재하면 False를 반환한다.

 

전방 일치 : startswith
문자열이 전방에서 일치하는지 비교하는 데에는 startswith가 사용된다. startswith는 문자열이 해당 패턴으로 시작하면 True, 시작하지 않으면 False를 반환한다. 패턴을 여러 개 지정할 경우 문자열이 이들과 하나라도 전방 일치한다면 True를 반환한다.

 

후방 일치 : endswith
문자열이 전방에서 일치하는지 비교하는 데에는 endswith가 사용된다. endswith는 문자열이 해당 패턴으로 끝나면 True, 끝나지 않으면 False를 반환한다. 패턴을 여러 개 지정할 경우 문자열이 이들과 하나라도 후방 일치한다면 True를 반환한다.

 

출처: https://cheris8.github.io/python/PY-Compare-String/

 다른 사람 답안 

궁금해서 다른 사람의 코드를 찾아보았는데 내가 사용한 두 함수를 합치면 다음과 같을 것 같다.

a, b = input().split()

answer = []
for i in range(len(b) - len(a) + 1):
    count = 0
    for j in range(len(a)):
        if a[j] != b[i + j]:
            count += 1
    answer.append(count)

print(min(answer))

출처: https://yoonsang-it.tistory.com/55

 

나도 합칠까 했지만 브루트포스 문제인만큼 실행 속도를 조금이라도 줄여보고자 case를 나눴다. 그런데 합친게 확실히 코드는 깔끔하다. 또 내 코드는 다른 함수를 계속 참조하기 때문에 메모리 면에서 이게 더 나을수도..?

그래서 제출해봤는데 사용된 메모리랑 시간이 완전 똑같았다. 결국 로직이 똑같아서 똑같나보다...

다른 사람들 코드를 더 찾아봤는데 다 비슷하게 푼 것 같다.