[백준 이분탐색] 2866 문자열 잘라내기

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

문제 링크

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

2866번: 문자열 잘라내기

 

🍒 문제 분석

가령 위와 같이 주어졌을 때,

각 열마다 문자열이 만들어지게 된다.

 

이후 1행에서 가져온 문자열을 제거하고난 뒤, 중복이 없다면 count에 1을 더하고. 중복이 있다면 count 값을 출력한다.

이후 2행, 3행, ... 마찬가지의 과정을 마지막까지 진행한다.

 

시간제한은 1초 이며, 문자열의 갯수와 문자열의 길이는 최대 1000 까지 주어진다.

 

🥑 시간 초과가 발생한 1번 째 시도

# R : 행의 갯수, C : 열의 갯수
R, C = map(int,input().split())
words = []
for _ in range(R):
    words.append(input())

length, count = C, 0
while True:
    word_list = set([tuple([words[i][j] for i in range(count+1, R)]) for j in range(C)])
    length = len(word_list)
    # 중복 문자열 발견 시 break
    if length != C:
        break
    count += 1
    # 모든 행 다 봤으면 break
    if count == R-1:
        break

print(count)

다음의 input 값을 받아서

 

mrvica 
mrvica
marica
mateja

 

1열은 지우고, 각각을 튜플로 (m,m,m), (r,a,a), (v,r,t), (i,i,e), (c,c,j), (a,a,a) 를 받았다.

이후 set 을 통해 집합을 만들어 중복이 있는지 여부를 검사하였다.

 

while 문을 통해 이 과정을 반복하였는데

 

튜플을 구성할 때 N * N번, 이 과정을 N 번  반복하므로. /( O( N^3) /) 만큼 연산하는 셈이다.

10억번 연산하는 셈이므로 당연하게도 시간초과가 났다.

 

제한시간은 1초이므로 2천만번 안에 연산을 끝내야했다.

 

 

🍓 2 번째 시도

import sys
input = sys.stdin.readline
# R : 행의 갯수, C : 열의 갯수
R, C = map(int,input().split())
words = [list(input().strip()) for _ in range(R)]

# for _ in range(R):
#     words.append(input().strip())

start, end = 1, R-1
while start <= end:
    mid = (start + end)//2

    word_list = set()
    for j in range(C):
        word = ''
        for i in range(mid, R):
            word += words[i][j]
        word_list.add(word)
    length = len(word_list)

    # 중복 문자열 발견 시
    if length != C:
        end = mid - 1
    # 중복 문자열 없을 때
    else :
        start = mid + 1


print(end)

1번째 시도에서 별달리 달라진 것은 없다.

다만 조회할 때 있어서 이진 탐색을 추가했다.

 

이러면 집합을 작성할 때, \( N^2 \)

이 과정을 \( logN \) 만큼 반복하게 된다.

 

최악의 경우 1000000 * log(1000) = 

약 천만번 연산을 하게 된다.

 

 

옳거니. 이진 탐색을 하는게 답이었다.

 

이진 탐색을 할 때는 늘 항상 헷깔리는게, 답을 start 값으로 해야할지. end로 해야할지. mid 로 해야할지가 너무 헷깔린다.

그래서 메모장에 직접 써봤다.

 

0번 행은 어차피 지우고 시작하므로 적지 않았다.

 

만약 답이 3 이라고 할때,

stage 1 : start =1, end = 11 따라서 mid = 6 (문자열이 중복)

stage 2 : start = 1, end = 5 따라서 mid = 3 (문자열이 중복되지 않음)

stage 3 : start = 4, end = 5 따라서  mid = 4 (문자열이 중복)

stage 4 : start = 4, end = 3 따라서 반복문 종료

 

답은 end 값이 되게 된다.

 

만약 3번째 열에서 start와 end 값이 둘다 3이었다면?

중복이 아니므로 다음 stage 에서 start가 4가 되게 되고 (start = mid+1)

따라서 마찬가지로 답은 end가 되게 된다.

 

따라서 end를 답으로 해서 출력하면 된다.

 

🍉 깨달은 점 및 정리

정말 오랜만에 풀어보는 이분 탐색 문제라 인덱싱에서 너무나 많이 해멨다.

특히나 리스트 컴프레헨션을 써서 간단하게 풀려고 하다가 헷깔려서 더 오래걸렸다.

 

< 이진 탐색 문제 풀이 >

1. start 와 end 를 세우고.

2. mid = (start+end)//2

3. start = mid + 1 또는 end = mid - 1 이라 놓고

4. start <= end 를 만족하지 않을 때까지 반복한다.

5. 정답을 end로 출력한다.

 

헷깔리면 위에 메모장 처럼 직접 써보면서 해보자.