📕문제
문제 설명
문자가 있는 m x n 테이블에서 주어진 단어가 존재하는지 판별하는 문제다. 인접한 셀은 연결된 것으로 순차적으로 방문한 문자로 단어를 이룰 수 있으며, 방문한 셀은 재방문할 수 없다.
예를들어 위와 같은 테이블에서 단어 ABCCED는 A를 시작으로 B, C, C, E, D를 거쳐 만들어질 수 있다.
📝풀이
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
def findNext(y, x, count):
if count == len(word):
return True
temp = board[y][x]
board[y][x] = "#"
up = y-1 >= 0 and board[y-1][x] == word[count] and findNext(y-1, x, count + 1)
down = len(board) > y+1 and board[y+1][x] == word[count] and findNext(y+1, x, count + 1)
left = x-1 >= 0 and board[y][x-1] == word[count] and findNext(y, x-1, count + 1)
right = len(board[0]) > x+1 and board[y][x+1] == word[count] and findNext(y, x+1, count + 1)
board[y][x] = temp
return up or down or left or right
for y in range(len(board)):
for x in range(len(board[0])):
if board[y][x] == word[0] and findNext(y, x, 1):
return True
return False테이블을 순회하며 주어진 단어의 시작 문자를 찾는다. 찾은경우 findNext()함수를 호출한다.
findNext()함수는 현재 위치 x, y와 지금까지 일치한 문자의 개수 count 를 매개변수로 갖는다.
- 만약 지금까지 일치한 문자의 개수가 주어진 단어의 길이와 같다면
True를 반환한다. - 같은 셀 중복 방문을 방지하기 위해
temp에 해당 셀의 문자를 저장하고,#로 대체한다. - 상하좌우로 범위에 벗어나지 않고, 단어가 일치한 경우 다음 단어를 찾기 위해 함수를 재귀호출한다.
각 결과의and연산을 통해 최종 검사값을 업데이트하게끔 한다. - 해당 셀에 대한 검사가 종료되면
temp를 이용해 복구한다. - 각 방향에 대한 결과 중 단 하나라도 참이 존재하면 단어가 존재한다는 뜻으므로 각 결과값에 대해
or연산을 한다.
결과
박수 두개를 받았지만 어떻게하면 Runtime을 저렇게 줄일 수 있나 궁금해져 코드를 분석해봤다.
먼저 단어의 길이와 테이블에 있는 문자의 개수를 비교했다.
if len(word) > len(board) * len(board[0]): return False- 단어의 길이보다 테이블에 존재하는 문자의 개수가 적으면
False를 반환한다.
이후 단어와 테이블에 존재한 문자의 빈도를 확인했다.
count = Counter(sum(board, []))
for char, freq in Counter(word).items():
if count[char] < freq:
return False- 카운터를 사용해 테이블과 단어에 존재하는 각 문자의 빈도수를 구하고, 각 문자에 대해 비교한다.
테이블에 존재한 문자의 수가 더 적으면 단어를 만들 수 없으므로False를 반환한다.
마지막으로 탐색 순서를 정했다.
if count[word[0]] > count[word[-1]]:
word = word[::-1]- 단어의 첫 글자보다 마지막 글자가 테이블에 더 많이 존재하면 단어를 뒤집는다.
이렇게 하면 탐색 경로를 더 줄일 수 있어 효율적으로 단어를 찾을 수 있게 된다.
최종 코드
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
def findNext(y, x, count):
if count == len(word):
return True
temp = board[y][x]
board[y][x] = "#"
up = y-1 >= 0 and board[y-1][x] == word[count] and findNext(y-1, x, count + 1)
down = len(board) > y+1 and board[y+1][x] == word[count] and findNext(y+1, x, count + 1)
left = x-1 >= 0 and board[y][x-1] == word[count] and findNext(y, x-1, count + 1)
right = len(board[0]) > x+1 and board[y][x+1] == word[count] and findNext(y, x+1, count + 1)
board[y][x] = temp
return up or down or left or right
if len(word) > len(board) * len(board[0]): return False
count = Counter(sum(board, []))
for char, freq in Counter(word).items():
if count[char] < freq:
return False
if count[word[0]] > count[word[-1]]:
word = word[::-1]
for y in range(len(board)):
for x in range(len(board[0])):
if board[y][x] == word[0] and findNext(y, x, 1):
return True
return False결과
최적화로 이렇게나 줄일 수 있다니..
앞으로는 문제를 풀고 최적화를 위해 고민하는 시간을 가져야겠다.
