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

[문제 출처]

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

1235번: 학생 번호

 

[문제 풀이]

0부터 9 사이의 숫자로 이루어진 학생 번호가 있고, 학생 번호를 뒤에 k자리 수만 남기고자 한다.

모든 학생의 번호가 다른 k자리 문자열을 만족하는 가장 작은 k를 찾는 문제이다,

 

학생 번호의 길이는 주어지지 않으며, 학생의 수와 학생 번호들이 주어진다.

 

k가 가장 작은 경우는 1로 마지막 한 자리로만 모든 학생이 구분되는 경우고,

k가 가장 큰 경우는 기존의 학생 번호일 때이다. 

 

가장 작은 k를 찾기 위해서 뒤에서부터 한자리, 두 자리, 세 자리,... 이런 식으로 한 자리씩 늘려가도록 코드를 작성했다.

k가 1일 때부터 각 학생번호의 문자열을 딕셔너리에 저장하였다. 만일 이미 같은 문자열을 키로 하는 값이 존재한다면, check변수를 1로 바꾸고 for문을 빠져나온다. check가 0일 때, 모든 문자열이 다른 것이므로 그때의 k값을 출력한다.

#1235

n = int(input())

s_id = []
for _ in range(n):
  s_id.append(input())
k = 0
for i in range(len(s_id[0])-1,-1,-1):
  k += 1
  check = 0
  cnt = dict()
  for j in range(n):
    if s_id[j][i:] in cnt.keys():
      check = 1
      break
    else:
      cnt[s_id[j][i:]] = 1
  
  if check == 0:
    print(k)
    break