백준 2866. 문자열 잘라내기

tose33 2023. 9. 2. 20:31

2866번: 문자열 잘라내기

첫 번째 줄에는 테이블의 행의 개수와 열의 개수인 R과 C가 주어진다. (2 ≤ R, C ≤ 1000) 이후 R줄에 걸쳐서 C개의 알파벳 소문자가 주어진다. 가장 처음에 주어지는 테이블에는 열을 읽어서 문자

www.acmicpc.net

행을 잘라내서 열을 읽기 때문에 우선 열을 읽어서 문자열을 만들자.

입력이 다음과 같다면

4 6
mrvica
mrvica
marica
mateja

열을 아래부터 읽으면 다음과 같은 문자열들이 만들어진다.

mmmm

aarr

trvv

eiii

jcca

aaaa

이 문제에서 결국 구하는건 문자열들을 앞에서 부터 읽어서 중복이 발생하는 최대 길이를 구하는 것이다.

위 예에서는 길이 2 일때가 아래 문자열로

aa 가 중복되기 때문에 2가 최대 길이다.

답은 문자열길이(4) - 최대중복발생길이(2) - 1 = 1 이 된다.

중복 여부는 set 자료구조를 사용했다.