문제
이번에는 학생들을 더욱 효율적으로 관리하기 위해 학생마다 고유한 학생 번호를 부여하기로 하였다. 학생 번호는 0부터 9 사이의 숫자로 이루어진 문자열로, 모든 학생들의 학생 번호는 서로 다르지만 그 길이는 모두 같다.
학생들의 번호를 부여해 놓고 보니, 김진영 조교는 어쩌면 번호가 지나치게 긴 것은 아닌가 싶은 생각이 들었다. 예를 들어 아래와 같은 7자리의 학생 번호를 보자.
| 이름 | 번호 |
|---|---|
| 오민식 | 1212345 |
| 김형택 | 1212356 |
| 이동호 | 0033445 |
이처럼 학생 번호를 굳이 7자리로 하지 않고, 뒤에서 세 자리만을 추려서 남겨 놓아도 모든 학생들의 학생 번호를 서로 다르게 만들 수 있다.
| 이름 | 번호 |
|---|---|
| 오민식 | 345 |
| 김형택 | 356 |
| 이동호 | 445 |
하지만 세 자리보다 적게 남겨 놓아서는 모든 학생들의 학생 번호를 서로 다르게 만들 수 없다.
학생들의 번호가 주어 졌을 때, 뒤에서 k자리만을 추려서 남겨 놓았을 때 모든 학생들의 학생 번호를 서로 다르게 만들 수 있는 최소의 k를 구하는 프로그램을 작성하시오.
링크 참조
문제 풀이
위에 문제에서 잘 설명 되어있듯이, 문자열을 잘랐을 때 구분 될 수 있는
최소 출력 개수(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 값을 증가시킨다.
그리고 시작점을 앞으로 당겨 문자열의 길이를 증가시킨 것을 다시 반복하게 한다.
이 과정으로 문자열의 개수를 구할 수 있다.
💌
후기
입출력 예시가 몇 개 없어서 제출할 때 두근두근 했는데 맞았길래
이게 맞아...................? 싶었던 문제 😋
