[백준] 2866번 : 문자열 잘라내기

2866번: 문자열 잘라내기

2866번: 문자열 잘라내기

📄 문제개요

• R개의 행과 C개의 열로 주어진 테이블이 입력으로 주어진다. 이 테이블의 원소는 알파벳 소문자이다.
• 각테이블의 열을 위에서 아래로 읽어서 하나의 문자열로 만들 수 있다.
• 2 ≤ R, C ≤ 1000

🤔 문제분석

• 문자는 최대 1000개와 문자의 길이는 1000을 갖을 수 있다.
• 완전탐색의 경우 최악의 경우 O($N^3$)이다.
  • 최악의 경우 1000번 반복하는데, 모든 문자의 중복을 확인( 1000 * 1000 ) 해야한다.
• O($N^2log(N)$)의 시간복잡도로 풀 수 있도록 생각을 해봐야 한다.
• words 라는 문자를 담은 배열이 있을때, words를 순회하는 word가 words안에 2개 이상 있는것을 찾아낸다면 중복이 있는것이다.
• words 라는 배열 크기는 N 이다.
• words를 순회하면서 word안에 있는 개수를 파악한다. ( 이분탐색 )
• 총 길이가 1000임으로 O($N^2log(N)$)의 시간복잡도로 풀 수 있다.

📝 의사코드

1. words를 입력받는다.
2. words를 정렬한다.
3. 문자열의 길이를 줄여보면서 중복값이 있는지 확인한다.
   1. 하나의 word가 words안에 중복값이 있는경우를 확인한다.
4. 중복값이 있다면 종료하고, 중복값이 없다면 +1 을 한뒤 3번으로 다시 간다.

💻 코드

import sys
input = sys.stdin.readline

R, C = map(int, input().split()) # 행, 열

words =['' for _ in range(C)]

for _ in range(R):
    temp = input().strip()
    for j in range(C):
        words[j] += temp[j]
        
words.sort()

def search_cnt(array, query):
    start = 0
    end = len(array) - 1
    left_idx = None
    while start <= end:
        mid = (start + end) // 2
        temp = array[mid]
        if temp >= query:
            left_idx = mid
            end = mid - 1
        else:
            start = mid + 1
            
    start = 0
    end = len(array) - 1
    right_idx = None
    while start <= end:
        mid = (start + end) // 2
        temp = array[mid]
        if temp <= query:
            right_idx = mid
            start = mid + 1
        else:
            end = mid - 1
            
    #print(right_idx, left_idx, query, array)
    return right_idx - left_idx + 1
        
start = 1
ans = 0
while start < R:
    flag = False
    words = [word[1:] for word in words]
    words.sort()
    for word in words:
        s_cnt = search_cnt(words, word)
        #print(s_cnt, word, start)
        if s_cnt > 1: # 중복이 있다면
            flag = True
            break
        
    if flag:
        break
    else:
        ans += 1
        
    start += 1

print(ans)

🎯 피드백 및 개선사항

• 해당문제는 문자를 정렬을 하지 않아서 어디서 문제가 발생하였는지 헛 시간을 투자했습니다.
• word를 한번 슬라이싱 한뒤, 정렬을 해야하는데 정렬을 하지 않아서 한참 해맸습니다.

words = [word[1:] for word in words]
words.sort()

❓다른사람은 어떻게 풀었을까?

• 문자열의 길이가 R일때, start = 0, end = R-1 로 두고 mid 값 이후의 문자열값을 비교한다.
• 만약 mid값 이후의 문자열중에서 중복값이 존재한다면 mid값의 크기를 낮춰야 한다.
• 만약 mid값 이후 문자열 중에서 중복값이 존재하지 않는다면 mid값의 크기를 키운다.
• 집합 자료구조를 활용하여 중복체크를 확인합니다. C와 집합 자료구조의 길이를 확인한다.

n, m = map(int,input().split(' '))
words = [''] * m
left,right = 0,n-1
    
for _ in range(n):
    for i, char in enumerate(input()):
        words[i] += char
        
def dup(mid):
    nodup = set()
    for word in words:
        nodup.add(word[mid:])
    return len(nodup) != m

answer = 0

while left <= right:
    mid = (left+right) // 2
    if dup(mid):
        right = mid-1
    else:
        answer = mid
        left = mid+1

print(answer)