[Python] 백준 2866번: 문자열 잘라내기(시간 복잡도 1등)

https://www.acmicpc.net/problem/2866

2866번: 문자열 잘라내기

 

 - (첫번째 해결 방법) 접근

문자열을 거꾸로 생각하고 여기에 Trie를 접목하였다.

 

import sys
input = sys.stdin.readline

class Node:
  __slots__ = ['childs']

  def __init__(self):      
    self.childs = {}

class Trie:
  __slots__ = ['root']

  def __init__(self):
    self.root = Node()

  def insert(self, strr):
    cur = self.root
    level = 1
    overrapped_level = 0

    for c in strr:
      if not cur.childs.get(c):    
        cur.childs[c] = Node() 
      else:
        overrapped_level = level

      cur = cur.childs[c] 
      level += 1
  
    return R - overrapped_level - 1
              

if __name__ == '__main__':
  R, C = map(int, input().split())
  strs = [str(input().rstrip()) for _ in range(R)]

  res = float('inf')   

  trie = Trie()        
  for strr in zip(*strs[::-1]):     
    res = min(res, trie.insert(strr))

  print(res)

 

 - (두번째 해결 방법) 접근

 row별로 지웠을 때 같은 문자가 없다면 0, 있다면 1이라고 해보자. 결과는 무조건 '0000...111111...'와 같은 식으로 나뉘게 된다.(물과 기름이 안 섞이듯이) 이는 마치 정렬된 것과 같으므로 이분 탐색을 할 수 있다.

 

 - (두번째 해결방법) 풀이

 이분 탐색을 1부터 R-1까지의 범위로 시작하며, 목적은 같은 문자열이 없는 row의 최대값을 구하는 것이다. is_there_same_string_pair()라는 함수로, mid 이상의 row에 같은 문자열 쌍이 한 개라도 있는지 확인한다. 여기서 참이 나오면 범위를 위쪽으로 올려주고, 거짓이면 범위를 아래로 내려주는데, 이로써 이분 탐색의 목적을 달성할 수 있다.

 is_there_same_string_pair() 함수는 각각의 문자열이 어느 위치(y)에 있는지를 c_to_y_indices에 저장해준 뒤, 특정 문자가 2회 이상 나왔을 경우 combination으로 y의 쌍을 선택하여 같은 문자열인지 체크해준다.

 

import sys, itertools
input = sys.stdin.readline
       
def is_same_string_pair(start_x, y1, y2):
  for i in range(start_x, R):
    if strs[i][y1] != strs[i][y2]:
      return False

  return True

def is_there_same_string_pair(x):
  c_to_y_indices = {} # row: aaba -> {'a':[0,1,3], 'b':[2]}         
  for j in range(C):
    c = strs[x][j]

    if c_to_y_indices.get(c):
      c_to_y_indices[c].append(j)
    else:
      c_to_y_indices[c] = [j]

  # Check if there is at least one same string pair
  for c, y_indices in c_to_y_indices.items():
    if len(y_indices) < 2: continue
                                      
    for y1, y2 in itertools.combinations(y_indices, 2):
      if is_same_string_pair(x+1, y1, y2):
        return True

  return False  

def find_biggest_index_with_no_same_string():          
  top, bottom = 1, R-1
  while top <= bottom:
    mid = (top + bottom)//2

    if is_there_same_string_pair(mid):  
      bottom = mid - 1  
    else:  
      top = mid + 1   

  return top - 1

if __name__ == '__main__':
  R, C = map(int, input().split())
  strs = [str(input().rstrip()) for _ in range(R)]

  print(find_biggest_index_with_no_same_string())