[python] 백준 1235번 - 학생 번호

희희구리·2023년 4월 21일

백준

목록 보기

12/21

문제

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

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

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

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

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

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

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

링크 참조

https://www.acmicpc.net/probl##em/1235

문제 풀이

위에 문제에서 잘 설명 되어있듯이, 문자열을 잘랐을 때 구분 될 수 있는
최소 출력 개수(k)을 찾으면 된다.

코드

N = int(input())
A = []

for _ in range(N):
    A.append(str(input()).strip())
    
count = 1
start = len(A[0]) - 1
end = len(A[0])

while start >= 0:
    ans = []
    for i in range(N):
        ans.append(A[i][start:end])
    if len(set(ans)) == N:
        break
    else:
        count += 1
    start -= 1
    
print(count)

N은 주어진 문자열의 개수, A에는 문자열을 담았다.
strip() 은 str 로 변환하여 입력값 받으면 뒤에 공백 생기기 때문에 없애준 것

start/ end을 이용하여 문자열을 슬라이스해 ans 배열에 담았다.
end은 고정한다. 뒤에서부터 하나 -> 두개 -> .. 로 늘려서 슬라이스 해야되기 때문!

슬라이스 한 배열을 ans에 배열에 넣는다. 이후, 해당 배열을 set을 이용하여 집합으로 만든다.
중복을 제거하기 위함이다. (Set은 중복된 요소 불가능)
set 요소가 입력받은 문자열의 개수와 같아졌을 때가 세 개의 고유 문자열이 생겼다고
해석할 수 있다. 그 경우 while문을 탈출한다.
만약 같아지지 않을 경우는 count 값을 증가시킨다.
그리고 시작점을 앞으로 당겨 문자열의 길이를 증가시킨 것을 다시 반복하게 한다.

이 과정으로 문자열의 개수를 구할 수 있다.