Greedy(8)_문자열(1120번)

작성일 | In

백준 1120

길이가 N으로 같은 문자열 X와 Y가 있다. X와 Y의 차이는 같지않은 문자열의 갯수를

A의 길이는 B의 길이보다 작거나 같다. 이 때, A와 B의 길이가 같으면서 A와 B의 차이를 최소로 하는 프로그램을 만들어라.

-> 차이를 최소한으로 만든다 -> 최대한 같게 만든다.

아이디어

문자열을 한 글자씩 끊어서 리스트로 바꾸기

str = "sdfsdfsdfsdf" a =list(str)를 사용하면 a라는 리스트에 한글자씩 끊어서 만든 리스트를 대입할 수 있다.

A와 B를 입력 받고, 그 차이만큼 앞에서 더해주고 뒤해서 더해준 뒤 for문을 한번 돌면서 각 리스트를 비교한다 그 값이 가장 최소인걸 출력한다

문제 이해를 잘못했다 내 접근 방법은 bcde aabcdefff 일 때 해결하지 못한다. 즉 앞에 더하기 연산을 했다면 무조건 앞에서만, 뒤 더하기 연산을 했다면 무조건 뒤에서만 하는 줄 알았지만. 둘 다 사용이 가능했다. 결국 for문을 돌면서 한칸씩 다 비교해봐야 한다.

b와 a의 string을 입력 받고, b-a만큼 for문을 돌면서, a[j]!=b[j+i]를 써서 확인이 가능하다. 이건 단순한 문제였어..

코드

import sys

a, b = sys.stdin.readline().split()

result = 9999999999  # 임의로 최대값을 넣어둠
for i in range(len(b)-len(a)+1):
    cnt = 0
    for j in range(len(a)):
        if(a[j] != b[j+i]):
            cnt += 1
    result = min(cnt, result)
print(result)

알게된 사실

  • a = list(str)을 사용하면 str이란 문자열이 각 문자로 쪼개진 채 리스트에 저장된다
  • min을 쓰려면 초기에 가장 높은 값을 임의로 설정해두어야 한다..

참고자료

[문자열을 한 글자씩 끊어서 리스트로 바꾸기]https://ghdwn0217.tistory.com/58 [답안 참고 블로그]https://deliorange.tistory.com/105

0%