문제
My Code
class Solution:
def isMatch(self, s: str, p: str) -> bool:
s = list(s)
p = list(p)
last_element = None
finished_with_asterist = False
while s and p:
print("first loop")
print(s)
print(p)
print("---")
ns = s.pop(0)
np = p.pop(0)
last_element = ns
if np == ".":
if p:
nnp = p[0]
if nnp == "*":
if (p[-1] in ):
return True
else:
return False
continue
elif np == "*":
finished_with_asterist = True
continue
while p:
print("second loop")
print(s)
print(p)
print("---")
nnp = p[0]
if nnp == "*":
if np != ns:
p.pop(0)
s.insert(0, ns)
finished_with_asterist = False
break
else:
while s:
nns = s[0]
if np == nns:
s.pop(0)
continue
else:
break
p.pop(0)
finished_with_asterist = True
else:
if ns == np:
break
else:
return False
while p:
print("final process P")
print(p)
print("---")
np = p.pop(0)
if np == ".":
return False
elif np == "*":
continue
else:
if p:
nnp = p.pop(0)
if nnp == "*":
continue
else:
return False
else:
if finished_with_asterist and (last_element == np):
break
else:
return False
print("before return answer")
print(s)
print(p)
print("---")
if (not s) and (not p):
return True
else:
if finished_with_asterist and (not s):
return True
elif (len(s) == 1):
ns = s.pop()
if finished_with_asterist and (ns == last_element):
return True
return False
Dicussions
먼저 나의 코드가 형편 없음을 고백한다.
그럼에도 불구하고 이 글을 작성하는 이유는 형편 없는 코드를 짜는 과정 속에서 깨달음 바가 있기 때문이다.
Approach
나는 처음에 모든 경우의 수를 처리할 수 있다면, 해당 문제를 풀 수 있다고 판단했다. 그래서 나는 크게 세 가지의 경우의 수를 나누고 문제를 풀었다.
1. Case Approach
- General Case
- 가장 보편적인 경우이다. 특정 데이터를 n이라는 변수로 치환해서 접근하는 방식이다. n이라는 변수로 인해 n이 포함되어 있는 구간들을 한번에 고려할 수 있는 접근 방식이기도 하다.
- 이 문제에서는 p 내부의 문자를 하나씩 고려할 때, p가 *인 경우, .(dot)인 경우, 문자인 경우로 나누어서 판단했다.
- Edge Case
- 가장 특수한 경우이다. 즉, 특정 경계값에 대한 고려이며 판단이다. 만약 n이라는 변수를 다룬다고 하면, n의 범위의 끝에 해당하는 값들을 고려하는 접근 방식이다.
- 이 문제에서는 *이나 .(dot)이 맨 끝 또는 맨 앞에 있는 경우 등으로 판단하여 접근하였다.
즉, 위와 같이 모든 경우의 수를 직접 if-else 문으로 catch 할 수 있다면 문제를 풀 수 있다고 판단하였다.
2. Index Approach
모든 경우의 수를 고려하기 위해선 순차적으로 P와 S를 순환할 필요가 있었다. 그래서 나는 index를 활용하여 순환하는 전략을 세웠다. 이 전략을 세우면서 고려했던 것들은 다음과 같다.
- index를 활용한 로직은 safe guard logic이 필수적이다.
- Index를 사용하는 전략은 필연적으로 Out of Index error에 대한 방어가 필요하다. 그렇기에 이를 위한 safe guard 로직을 구현해야 하는데, 이것이 index를 활용한 접근 방식의 큰 단점이기도 하다.
- 보통 반복문과 함께 인덱스를 활용하는데, 이때 수많은 경우의 수 중에서 어떤 경우에 Out of Index가 발생할 지 예측해야 한다. 그러나 이러한 예측은 매우 어렵다.
- Stack 또는 Queue를 활용하여 Index의 Safe guard logic을 단순화 하자.
- 반복문 내부의 인덱스를 내가 직접 컨트롤 하고 동시에 이를 위한 세이프 가드 로직까지 내가 짰을 때, 코드가 매우 복잡해진다는 것을 깨달았다. 왜냐하면 내가 직접 짠 코드는 기본적으로 임의의 원소로 접근하기 때문에 인덱스를 변화시킬 때 필요한 경우의 수를 단순화 하기 어려웠다.
- 그때 생각난 것이 바로 큐와 스택이다. 큐와 스택은 순환하는 로직에 대한 템플릿 코드가 잘 알려져 있다. 그렇기에 신뢰할 수 있는 코드였으며, 매우 간단한 모습이었다. 따라서 난 Out of Index error를 효과적으로 defence하기 위해 큐와 스택을 활용하여 P와 S라는 주어진 문자열을 순환하고자 하였다.
Problem
그러나 코드에서 볼 수 있듯이, 모든 경우의 수를 if-else문으로 catch 하는 것은 매우 어려웠다. 왜냐하면 코드를 실행할 때마다 edge case가 나왔고, 이후에는 내가 이해할 수 없는 edge case가 나오는 지경에 이르렀다. 즉, if-else 방식으로 모든 경우의 수를 처리하기에는 경우의 수가 너무 많았다. 보통 적합한 방식으로 문제에 접근했을 땐, 이러한 비효율이 발생하지 않는다.
특히 나를 힘들게 했던 것은 수식을 해석하는 방식이었다. 처음에는 왼쪽에서 오른쪽으로 p를 읽어가며 정규표현식을 처리했다. 이렇게 접근하니 "a*a"와 같은 패턴을 처리하지 못했다. 더 나아가선 "a*b*c"와 같은 패턴은 더더욱 처리하기 어려웠다. 그래서 오른쪽에서 왼쪽으로 p를 읽어가며 패턴을 처리하려고 하니 동일한 케이스에서 문제가 발생했다.
즉, 애초에 내가 생각한 방식 자체가 잘못된 것이다.
Solution
그래서 문제의 해설을 찾아보니 Tree구조를 이용하여 dfe와 같은 알고지름을 순환하여 데이터를 처리하는 것 같았다.
Takeaway
이 문제를 통해 나의 알고리즘적인 역량의 한계를 느꼈다. graph 관련된 알고리즘에 대한 역량을 보충할 필요가 있다. 알고리즘 공부 좀 하자!
또한 문제를 풀면서 중위표현식을 계산하는 알고리즘을 구현했던 경험이 떠올랐다. 어떻게 보면 컴퓨터 내부에서 수식을 처리할 땐 정규표현식의 문제처럼 동일하게 수식을 처리하지 않을까란 생각이 들었다. 그래서 컴퓨터 프로그램의 구조와 해석이란 책을 읽어야겠단 생각도 들었다.
다음 글에서는 이러한 부족한 점을 어떻게 채웠는지 서술해보겠다.
PS
요즘의 나는 기본기가 많이 부족함을 느낀다. 그래서 컴퓨터공학의 기본적인 지식을 채우기 위해서 오라클 구조 등을 공부하고 있으며, 앞으로는 시스템 성능을 측정하기 위해서 어떤 것들을 고려해야 하는지 Low level 관점에서 파악해보고자 한다.
High level의 코딩은 앞으로 인공지능이 더욱 잘하지 않을까? 요즘 들어 인공지능이 할 수 없는 일은 무엇일까 계속 고민하게 된다.
