[백준] 1235번 학생 번호 [Python]

 

 

주어진 학생들을 구분할 수 있을 만큼 학번을 앞에서부터 삭제했을 때, 가장 짧은 길이의 학번 만들기

 

문제

이번에는 학생들을 더욱 효율적으로 관리하기 위해 학생마다 고유한 학생 번호를 부여하기로 하였다. 학생 번호는 0부터 9 사이의 숫자로 이루어진 문자열로, 모든 학생들의 학생 번호는 서로 다르지만 그 길이는 모두 같다.

학생들의 번호를 부여해 놓고 보니, 김진영 조교는 어쩌면 번호가 지나치게 긴 것은 아닌가 싶은 생각이 들었다. 예를 들어 아래와 같은 7자리의 학생 번호를 보자.

이름번호

오민식	1212345
김형택	1212356
이동호	0033445

이처럼 학생 번호를 굳이 7자리로 하지 않고, 뒤에서 세 자리만을 추려서 남겨 놓아도 모든 학생들의 학생 번호를 서로 다르게 만들 수 있다.

이름번호

오민식	345
김형택	356
이동호	445

하지만 세 자리보다 적게 남겨 놓아서는 모든 학생들의 학생 번호를 서로 다르게 만들 수 없다.

학생들의 번호가 주어 졌을 때, 뒤에서 k자리만을 추려서 남겨 놓았을 때 모든 학생들의 학생 번호를 서로 다르게 만들 수 있는 최소의 k를 구하는 프로그램을 작성하시오.

 

입력
첫째 줄에는 학생의 수 N$($2≤N≤1,000$)$이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 학생의 학생 번호가 순서대로 주어진다. 모든 학생들의 학생 번호는 서로 다르지만 그 길이는 모두 같으며, 0부터 9 사이의 숫자로 이루어진 문자열이 주어진다. 문자열의 길이는 100보다 작거나 같다.

출력
첫째 줄에 구하고자 하는 가장 작은 k값을 출력한다.

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

 

학번은 리스트에 저장, 슬라이싱으로 앞 번호부터 지우기

학번이 학생을 구별할 있는 지는 그 리스트를 집합으로 변경해서 원소의 개수를 확인해보면 알 수 있다.

개수가 학생 수와 일치하면 구별할 수 있고, 개수가 줄어들면 구별하지 못한다는 의미이다.  

import sys
n = int(sys.stdin.readline())
st_id = [""]*n
for i in range(n):
    st_id[i] = sys.stdin.readline().rstrip()
    
    # 학번을 앞에서부터 지워가면서
    # set으로 변형했을 때, 학생 수가 감소하는 순간 그 직전 개수 출력
while 1:
    st_id = [s[1:] for s in st_id]
    if len(set(st_id)) != n:
        print(len(st_id[0])+1)
        break

 

예제 입력 1 

3
1212345
1212356
0033445

예제 출력 1 

3