Quazycode

4864_문자열_비교

6 min read

while 문 안에 rfind()를 쓸 때와 **해시 테이블(Dictionary)**을 쓸 때의 결정적인 차이를 설명해 드릴게요.

rfind(): N번 확인, - 총 작업량:

index = 0일때를 항상 생각할 것 무한 루프 (메모리 이슈) = While문 범위에 문제가 있다

. 왜 dict가 rfind()보다 압도적으로 빠를까요?

가장 큰 차이는 **“검색(Search)“**을 하느냐, **“조회(Lookup)“**를 하느냐의 차이입니다.

  • p.rfind('a') (검색): 파이썬이 패턴 문자열의 뒤에서부터 ‘a’가 나올 때까지 한 글자씩 다 대조해봅니다. 패턴이 1,000자라면 최악의 경우 1,000번을 읽어야 하죠. 이걸 while 루프가 돌 때마다 매번 하니까 시간이 엄청나게 걸리는 겁니다.

  • p_dict['a'] (조회): 이건 ‘색인(Index)‘이 있는 사전을 보는 것과 같습니다. 사전에 ‘a’라는 페이지를 딱 펼치면 바로 숫자가 적혀 있죠. 패턴이 1,000자든 1,000,000자든, 단 한 번에 결과를 가져옵니다.

비유를 들자면:

  • rfind: 도서관에서 책을 찾을 때, 1번 서가부터 끝까지 하나하나 제목을 읽으며 찾는 것.

  • dict: 도서관 안내 컴퓨터에 책 이름을 쳐서 “3번 서가에 있습니다”라는 결과만 보고 바로 달려가는 것.

그래서 **전처리(사전 만들기)**를 루프 밖에서 딱 한 번만 해두면, 루프 안에서는 엄청난 속도 차이가 나는 것입니다.

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
 
    p = input()
    len_p = len(p)
    p_end = len_p - 1 #index니까 -1
    # 전처리: p를 역순 dict로 미리 받아둔다, dict 컴프리헨션으로 for 문 돌면서 역 index 저장
    p_dict =  {char: (p_end - i) for i, char in enumerate(p)}
	# 무한 루프 방지: p_dict에서 가져온 값이 0일 경우 shift가 안 변할 수 있어요. 
    # 처음 index = 0인 위치에서 패턴 비교시는 괜찮은데 
    # (index = 0인 경우: 맨 끝 글자가 타깃과 비교 되므로 타깃과 패턴 글자가 일치한 것으로 판단 -> if문으로 빠짐)
    # 만약 그 위치에서 마지막 글자 일치해서 잘 가다가 else문으로 빠지면
    # index 값인 0만 계속해서 shift에 더해지므로 무한루프 -> index = 0일때만 shift 1 더해주기
    t = input()
    shift = 0
    answer = 0 
 
    while shift <= len(t) - len(p): #shift값 len(t)와 같거나 작을 때 -> 조건 위험
        #shift값이 len(t)-len(p)보다 작거나 같아야 무한 루프 안 걸림
        #왜 len(t)를 기준으로 하면 안 될까?
		#1. Index Error: t[shift + p_end]를 계산할 때 타깃의 범위를 벗어나서 프로그램이 죽을 수 있다.
        #2. 불필요한 연산: 정답이 나올 수 없는 구간(남은 글자가 패턴보다 적은 구간)까지 굳이 검사하게 된다.
        
        #타깃 알파벳과 패턴 맨 마지막 알파벳 일치 여부 확인
        if p[p_end] == t[shift+p_end]: #일치
            #이 위치에 p_end -= 1넣으면 1글자짜리 index = 0인건 들어오자 마자 -1되어서 체크가 안 됨
            if p_end ==0 and p[0] == t[shift]: #p_end가 0까지 와야만 맨 앞과 끝 문자만 보고 통과시키는 일이 없어짐
                answer = 1
                break
            else:
                p_end -= 1
                #print [shift]
        else: #불일치
            p_end = len_p - 1
            if t[shift+p_end] not in p_dict.keys(): # 타깃 알파벳이 패턴에 없음
                shift += len_p
            else: # 타깃 알파벳이 패턴에 있음
                if p_dict[t[shift+p_end]] == 0: #index = 0 무한 루프 방지
                    shift += 1
                else:
                    shift += p_dict[t[shift+p_end]]
    else:
        answer = 0
    print (f"#{test_case} {answer}")
 
'''
# while문 안에다가 계속 탐색하는 rfind()같은 거 넣으면 시간초과: O(MN)
        else: #불일치
            p_end = len(p) - 1
            if p.rfind(t[shift+p_end]) == -1: # 타깃 알파벳이 패턴에 없음
                shift += len(p)
            else: # 타깃 알파벳이 패턴에 있음
                shift += p.rfind(t[shift+p_end])
    else:
        answer = 0
    print (f"#{test_case} {answer}")
    '''```
 
파이썬에서 딕셔너리에 키가 있는지 확인할 때는 `.keys()`를 빼고 그냥 `if t[...] not in p_dict:` 라고 쓰는게 빠름. 
`.keys()`를 쓰면 별도의 리스트(혹은 뷰)를 거쳐야 하지만, 그냥 쓰면 해시 테이블을 직접 조회하기 때문에 더 빠르다