문제
R개의 행과 C개의 열로 이루어진 테이블이 입력으로 주어진다. 이 테이블의 원소는 알파벳 소문자이다.
각 테이블의 열을 위에서 아래로 읽어서 하나의 문자열을 만들 수 있다. 예제 입력에서dobarz adatak이 주어지는 경우 "da", "od", "ba", "at", "ra", "zk"와 같이 6개의 문자열들이 만들어지게 된다.
만약 가장 위의 행을 지워도 테이블의 열을 읽어서 문자열이 중복되지 않는다면, 가장 위의 행을 지워주고, count의 개수를 1 증가시키는, 이 과정을 반복한다. 만약 동일한 문자열이 발견되는 경우, 반복을 멈추고 count의 개수를 출력 후 프로그램을 종료한다.
테이블이 주어질 경우 count의 값을 구해보자.
import sys
input = lambda: sys.stdin.readline().strip()
# 한 열의 문자를 한 리스트로 만들기
# set에 추가해 set의 길이가 열의 개수와 같다면 count += 1
r, c = map(int, input().split())
arr = [""] * c
for _ in range(r):
s = list(input())
for i in range(c):
arr[i] += s[i]
count = 0
for i in range(1, r):
check_set = set({})
for j in range(c):
check_set.add(arr[j][i:])
if len(check_set) == c:
count += 1
else:
break
print(count)- r, c의 최대 범위가 1000 이므로 시간복잡도 O(N^2)의 풀이가 가능하다.
