문제 링크: https://www.acmicpc.net/problem/1235

Thumbnail: Photo by CX Insight (Unsplash)

풀이

'집합'을 이용한 풀이

집합이란, 동일한 원소가 중복되지 않는 컨테이너 자료구조입니다. (다른 원소를 저장할 수 있는 자료구조)

집합을 구현하는 방법은 이 글에서 다루진 않겠습니다. 이번 풀이에서는 파이썬에 내장된 set를 사용했습니다.

알고리즘은 다음과 같습니다.

• 잘라 쓸 수 있는 최소 길이(i) 를 1부터 학생 번호 문자열의 길이(num_length) 까지 늘려가면서 다음을 반복합니다:
  • 전체 학생 번호를 순회하며, 집합에 뒤에서부터 i만큼의 부분 문자열을 저장합니다.
  • 이후 집합의 원소 개수가 기존의 학생 번호의 수 \(N\)과 동일하다면, 그 길이가 문제에서 구해야 하는 \(k\)의 최솟값입니다.

전체 코드

input = open(0).readline
N = int(input())
min_length = 1
numbers = [input().strip() for _ in range(N)]
number_len = len(numbers[0])

s = set()
for i in range(1, number_len + 1):
    for n in numbers:
        s.add(n[-i:])
    if len(s) == N: # 뒤에서 i개까지 자른 부분 문자열이 N개의 학생 번호에 대해 모두 다를 때
        min_length = i
        break
    s.clear()
print(min_length)