매 횟수마다 한줄씩 줄어든다. 이말은 매 횟수마다 길이가 1줄어든 문자열을 저장해야 된다는 뜻이다.
R, C 가 각각 1000이므로 1000길이를 가지는 문자열이 1000개
하나씩 줄여가며 확인해보면 당연히 시간초과가 어떻게 해결할까?
제출코드
파이썬
import sys
input = sys.stdin.readline
from collections import defaultdict
N, M = map(int, input().split())
arr = [input().rstrip() for _ in range(N)]
class Node:
def __init__(self, word):
self.word = word
self.cnt = 0
self.children = defaultdict(int)
class Trie:
def __init__(self, N):
self.head = Node(None)
self.cnt = 0
def insrt(self, word):
now = self.head
for i in range(len(word)):
if now.children[word[i]] == 0:
now.children[word[i]] = Node(word[i])
else:
self.cnt = max(self.cnt, i+1)
now = now.children[word[i]]
myTrie = Trie(N)
for j in range(M):
word = ""
for i in range(N-1, -1, -1):
word += arr[i][j]
myTrie.insrt(word)
# 최대 N-1 줄을 지울 수 있음
print( N - 1 - myTrie.cnt)접근방법
트라이를 사용했다. 트라이 자료구조에 문자열을 저장하면 문자열을 줄여가며 저장할 필요가 없다.
트라이에 문자열을 넣으면서 중복되는 부분을 체크했다.
초기 모든 문자열의 길이는 행의 길이로 같다.
트라이에 문자열을 넣을때 뒤에서 부터 넣는다.
그리고 트라이는 트리구조로 이뤄져있다.
이렇게 했을때 트리의 깊이에서 중복되는 부분이 있다면 그 깊이의 길이에서 문자열이 중복된다는 얘기가된다.
다른 방법 (더 효율적)
트라이를 이용한 방법은 효율이 좋지 못했다. 통과는 했지만 처리시간이 오래 걸렸다. 실제 백준에서 가장 빠른 시간을 가진 코드와 처리시간 면에서 15배정도 차이가 나왔다.
그리고 시간이 빠른 코드들을 봤는데 접근이 되게 재밌었다. 바로 이분탐색을 이용한 방법이었다.
이분탐색은 정렬된 상태의 리스트에서 특정 값을 찾는 매우 효율적인 알고리즘이다.
그런데 이문제는 특정 값을 찾는게 아니다. 정렬도 안되어 있다. 어떻게 적용한걸까?
바로 문제에서 원하는 값 카운트를 이분탐색으로 찾았다.
뭔말인가 하니 R = 1000을 기준으로 카운트값은 최대 999번 나올 수 있다. 여서 1000개의 문자열을 하나하나 줄여가며 999번 비교하려다보니 시간초과 나온건데 이분탐색을 적용하면 logN의 복잡도니 10번으로 확인이 가능하다.
예를 들어 카운트 값이 700이 나오는 케이스라면.
500값으로 확인, 중복이 없다. 더 깊이 내려가본다.
-> 750으로 확인 중복이 있다. 위로 올라간다.
-> 625 확인 중복이 있다...
이런식으로 전형적인 이분탐색 방법으로 풀이가 가능했다.
지금까지 이분탐색을 리스트의 특정 원소를 찾는 방법으로만 생각했었는데
이렇식의 접근도 가능했다는게 되게 재밌게 느껴졌다.
