10문제 🎉 백준 11585 - kmp 알고리즘

문제

수원이와 친구들은 저녁 메뉴를 잘 선택하지 못한다. 배가 고픈 수원이가 보다 못해 메뉴를 정하곤 하는데 이마저도 반대에 부딪히는 경우에는 수원이가 원형 룰렛을 돌려 결정하곤 한다. 이 원형 룰렛으로 메뉴를 선택하는 방법은 매우 독특한데, 원형 룰렛을 돌린 뒤 12시부터 시계방향으로 읽어서 나오는 모양으로 저녁 메뉴를 결정한다. 원형 룰렛에는 정확히 N개로 나누어진 칸이 존재하고, 각 칸에는 알파벳 대문자 하나가 써져있다. 또한 원형 룰렛의 12시 방향에 존재하는 화살표는 칸 사이에 걸치는 일이 없이 항상 하나의 특정한 칸을 가리키게 되며, 원형 룰렛을 돌렸을 때, N개의 칸이 12시에 존재하게 될 확률은 모두 같다.

예시

입력

첫 번째 줄에는 원형 룰렛의 칸 수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 두 번째 줄에는 저녁 메뉴로 고기를 선택하게 되는 원형 룰렛의 모양이 12시 방향부터 시계방향으로 공백을 구분으로 한 글자씩 N개 주어진다. 세 번째 줄에는 현재의 원형 룰렛 모양이 12시 방향으로부터 시계방향으로 공백을 구분으로 한 글자씩 N개 주어진다.

9
I W A N T M E A T
E A T I W A N T M

출력

원형 룰렛을 돌렸을 때 오늘 저녁으로 고기를 선택하게 되는 확률을 기약분수 형태로 출력한다. 기약분수란 분자와 분모가 더 이상 약분이 안 되는 형태를 의미한다. 만약 룰렛이 어떤 곳에 멈춰도 고기를 먹을 수 있다면 1/1 을 출력한다. 원형 룰렛을 돌려 고기를 먹을 수 있는 경우의 수는 적어도 한 가지 이상 있기 때문에 분자가 0이 되는 경우는 없다.

1/9

푸는 법

kmp 알고리즘 : 문자열(s) 에서 특정 패턴(m) 을 효과적으로 (O(m+s) 만에) 찾아주는 문자열 알고리즘 (패턴이 존재한다면) KMP 알고리즘

최대공약수 구하기 : a,b의 최대공약수는 a,b 중 큰 수를 작은 수로 나눈 나머지와 a,b 중 작은 수의 최대공약수와 같다 이용 (사실 이 방법이 코드칠 때 너무 공식처럼 써서 그냥 외우다가 이번에 유클리드 호제법이라는 명칭을 알게 되었다)

I W A N T M E A T
E A T I W A N T M

에서 I W A N T M E A T 을 string 으로 보고 E A T I W A N T M 을 pattern 으로 본다면 begin 이 1 증가한다는 의미는 룰렛이 한 번 알파벳 인덱스가 바뀌어서 멈출만큼 회전했다는 뜻으로 볼 수 있다. 즉 E A T I W A N T M 에서 시계방향 회전을 시작한 룰렛이 멈추는 각 시점은 KMP 알고리즘에서 begin 이 1 증가할 때이다.

kmp 연습하기 위해서 선택한 문제여서 방법은 알았지만 애초에 kmp 알고리즘이 이해하는데 너무너무 어려웠기 때문에 많이 헤맸다.

구현 방법에서 잘못 생각했던 부분, 주의할 부분을 정리하자면

• kmp 에 걸리는 while 조건 (해당 문제 vs 원 kmp 알고리즘)

백준 문제 : while b<=문자열 길이(=패턴 길이)

원래 kmp 알고리즘 : while b<=문자열 길이-패턴 길이

b도 커지고 m도 커지므로 제한을 해줘야 함, b랑 m 하나라도 범위를 벗어나면 while 종료해야한다.

(여기서 b는 begin, m은 match)

원 알고리즘에서는 패턴 길이가 일반적으로 문자열 길이보다 짧고 해당 문자열 범주 내에 패턴이 어디에 존재하는지를 찾는 문제이기 때문에 애초에 문자열 내 비교를 시작하는 begin 의 인덱스가 패턴의 제일 끝 인덱스보다도 넘어가버리면 문자열에서 남는 부분은 애초에 패턴보다 짧으므로 그 이후부터는 패턴을 아예 찾을 수 없는 인덱스로 보고 종료해주면 된다. 그런데 이 문제에서는 룰렛이 시계 방향 한 바퀴 회전을 마치고 원래 있던 자리로 돌아올 때까지 begin이 하나 증가할 때마다 반드시 저녁메뉴 문자열이 나왔는지 매번 확인해줘야하기 때문에 문자열 길이 끝까지 검사해야한다. (단 kmp 알고리즘이므로 마지막 인덱스까지 검사해주되 그 과정에서 사이사이 뛰어넘을 부분을 뛰어넘는 것 ! 촘촘하게 모든 인덱스를 검사하지 않는 것이 kmp 알고리즘의 핵심 !)

또 m 도 끝없이 증가할 수 있으므로 m<=len(self.pattern) - 1 이렇게 조건을 걸어줘야하지만 아예 안에 중첩 if 문을 걸어서 match 가 패턴 길이만큼 도달했을 때 match를 다음 검사에 맞게끔 재세팅해주었다.

• failure 함수에서 값이 0인 것은 아무 도움이 되지 않는다

  결국 kmp 알고리즘은 전체 문자열에서 일정 길이의 prefix와 suffix가 일치하는 부분 문자열이 있을 것이고 이를 활용하겠다는게 요지이다. 그리고 prefix와 suffix가 전체 문자열을 슬라이싱한 각 부분에서 얼마나 일치하는지는 failure 함수의 해당 인덱스에 저장된 값으로 알 수 있다. 즉 값이 0인 failure 함수의 key 는 애초에 kmp 에서 전혀 활용할 수가 없으므로 쓸모가 없다. failure 함수를 구할 때 이 부분을 생각한다면 failure 함수 자체가 문자열도 패턴,패턴도 패턴으로 되어있는 또 하나의 kmp 알고리즘이라는 것을 유추할 수 있다. 따라서 kmp 에서 애초에 패턴이 되기 그른 애들은 다 뛰어넘는 것이 핵심이듯이 failure 함수를 구현할 때도 match가 0이어서 쓸모없는 애들은 뛰어넘을 수가 있다.

• failure 함수에 걸리는 while 문의 조건

  백준 문제, 원 kmp 알고리즘 : while b+m<패턴의 길이

  failure 함수 f(begin+match-1)=match 에서 begin+match-1은 어디 인덱스까지 슬라이싱한 것인지를 말해준다. 아무리 m 이 점점 늘어도 문자열 맨 마지막 인덱스까지 슬라이싱했을 때 (=즉 하나도 슬라이싱 안 한 전체 문자열) 에서 prefix와 suffix가 일치하는 최장 prefix 를 구하는 데 그쳐야한다. 그 이상으로는 m 이 증가하면 안 된다.

• 한번 패턴이 존재하는 부분을 발견한 후 그 후의 검사는 ?

  이 부분이 포인트인 것 같다. 사실 여기를 잘못해서 kmp 를 썼는데도 4번이나 시간초과가 떴다.

  패턴을 발견한 후에도 failure 함수를 그대로 활용할 수 있음을 깨달았다.

  가령 문자열 : p a n a m a b a n a n a , 패턴 : a n a 가 있다고 할 때

  p ✔️a n a m a b a n a n a

  ✔️a n a

  이렇게 begin 1 에서 이미 패턴을 발견해주었어도 바로 다음 인덱스인 n 을 검사하는게 아니라 (kmp알고리즘의 원리를 그대로 생각해보면 애초에 a로 시작하지도 않는 애를 검사할 필요가 없다) failure 함수를 사용해서 3번째 a로 시작하는 부분부터 검사하면 된다. 패턴 ana 의 failure(2)=1 (‘a’) 이므로 😀

코드 1 ) input 값 저장하는 부분

import sys
input=sys.stdin.readline
class Dinner:
    def read(self):
        self.move_n=int(input())
        self.string=list(map(str,input().split()))
        self.pattern=list(map(str,input().split()))
        self.failure={}
        self.count=0

코드2) kmp 알고리즘 부분

def kmp(self):
        self.Failure()
        b=1
        m=0
        while b<=self.move_n:
            if self.string[(b+m)%(self.move_n)]==self.pattern[m]:
                m+=1
                if m==len(self.pattern):
                    self.count+=1
                    try:
                        b=b+m-self.failure[m-1]
                        m=self.failure[m-1]
                    except KeyError:
                        b+=1
                        m=0
            else:
                #패턴과 한 글자만 일치하거나 아예 처음부터 불일치하는 경우
                if m<=1:
                    b+=1
                    m=0
                #혹시 모르니깐 try로
                else:
                    try:
                        b=b+m-self.failure[m-1]
                        m=self.failure[m-1]
                    except KeyError:
                        b+=1
                        m=0

failure 함수도 kmp 알고리즘처럼 값이 0 인 애들은 저장 안 하고 다 스킵했기 때문에 애초에 값이 0인 애들은 저장되어있지 않다. 활용할 수 없으므로 ! 그런데 match 가 0인 부분도 활용할 수 있나 failure 딕셔너리에 접근해서 에러가 나는 경우를 방지하기 위해서 try ,except 로 해결하였다. 즉 except 에 걸리면 failure 로 검사 스킵하지 못하는 부분이니까 빠짐없이 검사해라 ! 🤓 의 의미이다.

사실 코드 이것보다 훨씬 가볍게 구현할 수 있을 것 같다. 더 좋은 방법 있으면 공유해주시면 정말 감사하겠습니다 🙆‍♀️

코드3) failure 함수 부분

def Failure(self):
        b=1
        m=0
        twin=self.pattern
        while b+m<len(self.pattern):
            if self.pattern[b+m]==twin[m]:
                m+=1
                self.failure[b+m-1]=m
            else:
                if m<=1:
                    b+=1
                    m=0
                #혹시 모르니깐 
                else:
                    try:
                        b=b+m-self.failure[m-1]
                        m=self.failure[m-1]
                    except KeyError:
                        b+=1
                        m=0

failure 함수도 결국 match 값을 이용하는 kmp 알고리즘이라는 것을 생각하면 코드가 while 문 조건 걸리는 부분 빼면 거의 유사하다.

코드4) gcd 부분

def gcd(self,x,y):
        while y:
            x,y=y,x%y
        return x

코드5)정답 도출 부분

def Answer(self):
        if self.pattern.count(self.pattern[0])==len(self.pattern):
            print('1/1')
            return
        else:
            self.kmp()
            d=self.gcd(self.move_n,self.count)
            Answer=str(self.count//d)+'/'+str((self.move_n)//d)
            print(Answer)

애초에 룰렛의 모든 글자가 동일하다면 당연히 룰렛이 얼만큼 회전해도 100% 그 메뉴를 먹는 것이기 때문에 시간 단축하려고 if 문을 추가하였다.

전체 코드

import sys
input=sys.stdin.readline
class Dinner:
    def read(self):
        self.move_n=int(input())
        self.string=list(map(str,input().split()))
        self.pattern=list(map(str,input().split()))
        self.failure={}
        self.count=0
    
    def kmp(self):
        self.Failure()
        b=1
        m=0
        #b도 커지고 m도 커지므로 제한을 해줘야 함, b랑 m 하나라도 범위를 벗어나면 while 종료
        #begin 은 pattern 이 string 모든 index를 돌면서 일치 갯수를 세어야 함
        #pattern 중 얼마나 일치하는지 보는게 m이기 때문에 m도 pattern 길이를 넘을 수가 없음
        while b<=self.move_n:
            if self.string[(b+m)%(self.move_n)]==self.pattern[m]:
                m+=1
                if m==len(self.pattern):
                    self.count+=1
                    try:
                        b=b+m-self.failure[m-1]
                        m=self.failure[m-1]
                    except KeyError:
                        b+=1
                        m=0
            else:
                #패턴과 한 글자만 일치하거나 아예 처음부터 불일치하는 경우
                if m<=1:
                    b+=1
                    m=0
                #혹시 모르니깐 try로
                else:
                    try:
                        b=b+m-self.failure[m-1]
                        m=self.failure[m-1]
                    except KeyError:
                        b+=1
                        m=0
    
    def Failure(self):
        b=1
        m=0
        twin=self.pattern
        while b+m<len(self.pattern):
            if self.pattern[b+m]==twin[m]:
                m+=1
                self.failure[b+m-1]=m
            else:
                if m<=1:
                    b+=1
                    m=0
                #혹시 모르니깐 
                else:
                    try:
                        b=b+m-self.failure[m-1]
                        m=self.failure[m-1]
                    except KeyError:
                        b+=1
                        m=0
                    
    def gcd(self,x,y):
        while y:
            x,y=y,x%y
        return x
    
    def Answer(self):
        if self.pattern.count(self.pattern[0])==len(self.pattern):
            print('1/1')
            return
        else:
            self.kmp()
            d=self.gcd(self.move_n,self.count)
            Answer=str(self.count//d)+'/'+str((self.move_n)//d)
            print(Answer)
    
    
    
    
dinner=Dinner()
dinner.read()
dinner.Answer()

해당 문자열 내 인덱스 하나하나를 검사해서 패턴이 있는지를 찾는다면 이중 for 문을 써야하므로 시간 복잡도가 O(패턴 길이*문자열 길이) 가 나온다. 반면 kmp 에서는 while 문 각각 패턴 길이,문자열 길이만 고려해주면 되므로 O(패턴 길이 + 문자열 길이) 이다. 🙂

마무으리

사실 kmp 알고리즘 이렇게 복잡한 거를 내가 단번에 구현했을리가 없다 ㅋㅋㅋ 당연히 예전에 kmp 처음 공부할 때 구글링도 해보고 이것저것 머리를 싸매고 만든 부분 꺼내다가 거의 바꿔서 썼다. 최대공약수도 그냥 잘 알려진 코드 공식처럼 외워서 사용하였다 ! 하지만 문자열 알고리즘 문제에서 kmp 가 거의 치트키 (맞나?!) 라고 생각이 들어서 이렇게 익숙해지면 좋을 것 같다 :)

사실 오늘 이진탐색트리 자료구조를 공부할 순서였는데 애초에 너무 공부를 늦게 시작해서 하루 루틴이 망가졌다. 그래서 문제 하나라도 풀고 쉬자라는 생각으로 이 문제를 풀게 되었다. bfs,dfs 복습하고 앞부분 알고리즘 복습할 것부터 차근차근 해야하는데 오늘 어떻게 하다보니까 문자열을 풀게 된 것 같다.

그리고 드디어 백준 10문제 풀었당 😆 그러니까 일요일은 뭐하고 놀까 흐흐

TMI

맥분투 하려다가 다른 아이콘들로 우분투를 꾸며봤는데 좀 유치한 것 같기도 하다. 분명 컴퓨터인데 아이콘 이렇게 하니까 핸드폰 느낌이 난다. 리눅스 공부하면 할 수록 매력있는 것 같다. 맥 »리눅스>윈도우 순으로 좋다. 이거랑 한글 입력 헤매느라고 오전 시간을 다 까먹었지만 😣 뿌듯하당