[파이썬/python] 백준 - 1235 학생 번호

문제

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

---

문제 설명

1.   학생들에게 고유한 학생 번호를 부여한다.
   1. 학생 번호는 0에서 9 사이의 숫자로 이루어진 문자열이다.
   2. 학생들의 고유 번호는 서로 다르지만 그 길이는 모두 같다.
2. 학생들의 고유 번호가 주어졌을 때, 뒤에서 k자리만 추려서 남겨 놓았을 때 모든 학생들의 학생 번호를 서로 다르게 만들 수 있는 최소의 k를 구한다.

 

---

풀이

학생 번호들을 뒤에서부터  i개씩 파싱해서 서로 비교한다. 

set에 모든 학생번호를 넣고 set의 크기가 학생의 수와 동일할 때 i를 출력했다.

 

1. 문자열의 길이만큼 역으로 반복한다.
2. res에 현재 길이까지 슬라이싱 한 문자열을 넣는다.
3. 길이가 N과 동일하다면 현재 길이를 출력한다.

---

코드

import sys
input = sys.stdin.readline

N = int(input())

std = [list(input().strip()) for _ in range(N)]

n = len(std[0])

for i in range(n-1,-1,-1):
    res = set()
    for j in range(N):
        res.add(''.join(std[j][i:]))
    if len(res) == N:
        print(n-i)
        exit()

---

시간복잡도

• 최악의 경우 $O(N^2)$의 시간복잡도가 소요된다.
• 따라서 시간복잡도는 $O(10^6)$