문자열 비교 Python(SW Expert Academy)

난이도 : D2

문제번호 : 4864

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDN86AAXw5UW6&subjectId=AWOVGOEKqeoDFAWg#

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

두 개의 문자열 str1과 str2가 주어진다. 문자열 str2 안에 str1과 일치하는 부분이 있는지 찾는 프로그램을 만드시오. 예를 들어 두 개의 문자열이 다음과 같이 주어질 때, 첫 문자열이 두번째에 존재하면 1, 존재하지 않으면 0을 출력한다.   ABC ZZZZZABCZZZZZ 두번째 문자열에 첫번째 문자열과 일치하는 부분이 있으므로 1을 출력.   ABC ZZZZAZBCZZZZZ 문자열이 일치하지 않으므로 0을 출력.

입력

첫 줄에 테스트 케이스 개수 T가 주어진다.  (1≤T≤50) 다음 줄부터 테스트 케이스 별로 길이가 N인 문자열 str1과 길이가 M인 str2가 각각 다른 줄에 주어집니다. (5≤N≤100, 10≤M≤1000, N≤M)

출력

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

예시

입력	출력
3 XYPV EOGGXYPVSY STJJ HOFSTJPVPP ZYJZXZTIBSDG TTXGZYJZXZTIBSDGWQLW	#1 1 #2 0 #3 1

---

2. 문제풀이

파이썬 3일차 연습문제 중 하나인 문자열 비교 문제이다. 파이썬의 내장 함수기능을 이용하면 쉽게 풀 수 있다. 처음 입력되는 문자열이 두번째 문제열에 포함되는지 확인하면 되는 문제인데 in 기능을 이용하면 바로 풀린다.   밑에 추가적으로 보이어 무어 알고리즘을 이용한 풀이를 올렸다.

---

3. 소스코드

#D2 4864 문자열 비교
T = int(input())
for t in range(1, T+1):
    s = input()
    string = input()
    result = 0
    if s in string:
        result = 1
    print("#{} {}".format(t, result))

 

번외 : 보이어 무어 알고리즘을 이용한 풀이

 

#보이어 무어 알고리즘
def pattonmatch(p, t):
    pattonLength = len(p)
    targetLength = len(t)
    #인덱스 위치를 나타내는 변수
    i = 0
    #두 길이의 차만큼만 반복한다.
    while i <= targetLength-pattonLength:
        #뒤에서부터 확인하므로 길이 -1
        j = pattonLength - 1
        # 반복하여 확인
        while j >= 0:
            #패턴이 일치하지 않는다면
            if p[j] != t[i+j]:
                #이동할 거리를 계산한다.
                #비교할 문자는 처음 비교하던 위치의 뒷글자를 넘긴다.
                st = find(p, t[i + pattonLength - 1])
                break
            #위의 조건이 무시되었다면 맞는것이므로 앞으로 이동한다.
            j = j - 1
        #-1까지 갔다면 모든 문자열이 일치한다.
        if j == -1:
            return True
        #j가 -1이 되지않았다면 문자열이 일치하지 않은것이므로
        #위에서 계산한 이동값만큼 인덱스에 더해준다.
        else:
            i += st
    #모든 반복동안 찾지못했다면 일치하는 부분이 없다.
    return False
 
#맞는 위치를 찾아 이동한다.
def find(p, v):
    #원래는 -1부터 시작하는데 처음부분은 무조건 맞지않으므로
    #-2부터 시작하여 불필요한 연산을 줄인다.
    for i in range(len(p)-2, -1, -1):
        if p[i] == v:
            return len(p) -i -1
    return len(p)
 
for t in range(1, int(input())+1):
    s = input()
    string = input()
    result = 0
    if pattonmatch(s, string):
        result = 1
    print("#{} {}".format(t, result))