1120. [Python]문자열

1. 문제

 

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

1120번: 문자열

 

2. 접근 방법

 

• 시간 제한: 2초
• 메모리 제한: 128MB
• 브루트포스

 

3. 파이썬 코드

 

word_1,word_2 = input().split()
# 첫번째 단어와 두번째 단어의 길이가 같은지 아닌지 판단
if len(word_1) == len(word_2):
    cnt = 0
    # 길이가 같은경우 한개의 길이를 반복문을통해서 탐색
    for i in range(len(word_1)):
        if word_1[i] != word_2[i]:
            # 다른경우 cnt 라는 변수를 +1 해줌
            cnt += 1
    # 다른 부분의 갯수를 출력
    print(cnt)
# 단어의 길이가 다른경우
else:
    # 첫번째 단어의 길이와 두번째 단어의 길이를 각각 변수에 저장
    word_1_length = len(word_1)
    word_2_length = len(word_2)
    # 정답 리스트에 값출력
    ans_list = []
    # 두번째 단어와 첫번째 단어의 길이차 +1 범위까지 반복분 시행
    for j in range(word_2_length-word_1_length+1):
        # cnt 변수에 0 을 저장
        cnt = 0
        # 첫번째 단어의 길이만큼 반복문 시행
        for k in range(word_1_length):
            # 첫번째 단어와 두번째단어의 시작값을 변경해가며 값을 비교
            if word_1[k] != word_2[j+k]:
                # 다른 경우 갯수를 체크
                cnt += 1
        # 정답 리스트에 반복문을 통한 갯수를 체크한 변수 추가
        ans_list.append(cnt)
    # 그 중 제일 작은 값의 변수를 추가
    print(min(ans_list))

 

4. 문제를 풀고난 후 생각

 

• 문제에서 제시한 조건으로 A의 단어의 앞이나 뒤에 문자를 추가하는 것만 조건으로 주어졌다.
• 그리고 들어오는 인풋값들로 A의 길이가 B의 길이보다 작거나 같기 때문에 길이가 같은 경우와 작은경우를 나눠서 생각했다.
• 길이가 같으면 문자열 한개한개 비교해가며 다른부분을 체크하면 되기 때문에 구현은 간단했다.
• 길이가 다를 경우 A라는 문자열 전체를 가지고 B라는 문자열의 처음부터 끝까지 길이가 다른것을 확인하여 그 값들 중 제일 작은 값을 출력하면 문제에서 원하는 해답이 된다.
• 이러한 생각을 한 이유는 A의 문자열을 가지고 앞, 뒤 부분에 문자열을 추가하는 것이 B에 있는 문자열을 추가해야 최소로 다른 값인 경우를 찾을 수 있기 때문에 A라는 문자열 자체가 B라는 문자열에서 몇개나 중복되는지를 확인해야 했다.

• 이런 방식으로 다른 갯수를 체크하여 최소값을 출력하면 답이된다.

5. 문제를 푸는데 도움이 되는 지식

 

• 브루트 포스