IT-garden

문제

길이가 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의 차이를 최소가 되도록 했을 때, 그 차이를 출력하시오.

예제 입력과 출력

알고리즘 분류

그리디 알고리즘

브루트 포스

문자열 처리

시뮬레이션

정답

a,b=input().split(' ')

c=0
d=[]

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

print(min(d))

a a b a b b c
a d a a b c
   1 1      1

a a b a b b c 
  a d a a b c
     1   1

b가 a보다 긴 경우 남는 공간은 같은 문자를 넣는다고 생각해서 비교하지 않습니다.

백준 알고리즘 1120번 : www.acmicpc.net/problem/1120

문제

세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한다. 예를 들어, 문서가 abababa이고, 그리고 찾으려는 ababa라면, 세준이의 이 함수는 이 단어를 0번부터 찾을 수 있고, 2번부터도 찾을 수 있다. 그러나 동시에 셀 수는 없다.

세준이는 문서와 검색하려는 단어가 주어졌을 때, 그 단어가 최대 몇 번 중복되지 않게 등장하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 문서가 주어진다. 문서의 길이는 최대 2500이다. 둘째 줄에 검색하고 싶은 단어가 주어진다. 이 길이는 최대 50이다. 문서와 단어는 알파벳 소문자와 공백으로 이루어져 있다.

출력

첫째 줄에 중복되지 않게 최대 몇 번 등장하는지 출력한다.

예제 입력과 출력

알고리즘 분류

그리디 알고리즘

문자열 처리

탐색

정답

a=input()
b=input()
c=0
i=0

while True:
    if i > len(a):
        break
    
    if a[i:i+len(b)] == b:
        i=i+len(b)
        c=c+1
    else:
        i=i+1
    
print(c)

백준 알고리즘 1543번 : https://www.acmicpc.net/problem/1543