[백준] 2866번 - 문자열 잘라내기 (파이썬)

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

 

# 문자열 잘라내기
from collections import defaultdict
R, C = map(int, input().split())
arr = [list(input()) for _ in range(R)]

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

    # 문자열 중복 확인
    isOK = True
    dict = defaultdict(int)
    for j in range(C):
        temp = ''
        for i in range(mid, R):
            temp += str(arr[i][j])
        if not dict[temp]:
            dict[temp] += 1
        else:
            isOK = False
            break

    if isOK:
        result = mid
        start = mid + 1
    else:
        end = mid - 1

print(result)

 

이분탐색
1. 입력을 받고, R의 처음과 끝으로 start와 end 설정
2. 이분탐색
    - 문자열을 해시(딕셔너리)를 이용해서 중복 확인
    - 만약 중복되지 않는다면 start = mid + 1, result = mid
    - 중복되었다면 end = mid - 1
3. result 출력

 

한 번 문장열이 중복되면 그 이후는 당연히 문자열이 중복이 된다. 연속성으로 인해 이분탐색 가능

input :
5 6
mrvica
mrvica
marica
mateja

output:
1

풀이:
marica에서 mm, aa, rt, ie, cj, aa로 aa가 중복으로 나온다.
이는 그다음 mateja에서 a, t, e, j, a로 aa에서 맨 앞 문자를 뺀 a가 중복으로 나온다.
따라서 마지막으로 중복이 등장하지 않는 1행이 답이다.