문제
이번에는 학생들을 더욱 효율적으로 관리하기 위해 학생마다 고유한 학생 번호를 부여하기로 하였다. 학생 번호는 0부터 9 사이의 숫자로 이루어진 문자열로, 모든 학생들의 학생 번호는 서로 다르지만 그 길이는 모두 같다.
학생들의 번호를 부여해 놓고 보니, 김진영 조교는 어쩌면 번호가 지나치게 긴 것은 아닌가 싶은 생각이 들었다. 예를 들어 아래와 같은 7자리의 학생 번호를 보자.
이름 | 번호 |
오민식 | 1212345 |
김형택 | 1212356 |
이동호 | 0033445 |
이처럼 학생 번호를 굳이 7자리로 하지 않고, 뒤에서 세 자리만을 추려서 남겨 놓아도 모든 학생들의 학생 번호를 서로 다르게 만들 수 있다.
이름 | 번호 |
오민식 | 345 |
김형택 | 356 |
이동호 | 445 |
하지만 세 자리보다 적게 남겨 놓아서는 모든 학생들의 학생 번호를 서로 다르게 만들 수 없다.
학생들의 번호가 주어 졌을 때, 뒤에서 k자리만을 추려서 남겨 놓았을 때 모든 학생들의 학생 번호를 서로 다르게 만들 수 있는 최소의 k를 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 학생의 수 N(2≤N≤1,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 학생의 학생 번호가 순서대로 주어진다. 모든 학생들의 학생 번호는 서로 다르지만 그 길이는 모두 같으며, 0부터 9 사이의 숫자로 이루어진 문자열이 주어진다. 문자열의 길이는 100보다 작거나 같다.
출력
첫째 줄에 구하고자 하는 가장 작은 k값을 출력한다.
코드
n = int(input())
sn = [input() for _ in range(n)]
for k in range(1, 101):
new_sn = set()
duplication = False
for j in sn:
own_num = j[len(j)-k:]
if own_num in new_sn:
duplication = True
break
else:
new_sn.add(own_num)
if duplication:
continue
else:
print(k)
break
k를 1부터 101까지 증가시키며 아래의 과정을 반복한다.
- 뒤에서부터 k만큼 자른 학생 번호를 저장할 집합 new_sn을 만든다.
- 문자열로 저장했던 학생 번호 sn을 살펴보며 뒤에서부터 k만큼 슬라이싱한다. 이 결과가 이미 new_sn 집합에 있다면 k만큼 잘랐을 때 고유한 번호를 가질 수 없는 것이므로 duplication을 True로 바꾸고 반복문을 탈출한다.
- duplication이 True라면 중복이 발생한 것이므로 k를 증가시켜봐야 한다. 그러므로 continue하고, 그렇지 않다면 지금 k값으로 학생 번호를 잘랐을때 고유하게 만들 수 있다는 뜻이므로 지금 k 값을 출력하고 반복문을 탈출한다.
'문제풀이 > 구현' 카테고리의 다른 글
[Python/파이썬] 백준 14891번 톱니바퀴 (0) | 2024.01.13 |
---|---|
[Python/파이썬] 백준 9242번 폭탄 해체 (0) | 2024.01.12 |
[Python/파이썬] 백준 21756번 지우개 (1) | 2023.12.16 |
[Python/파이썬] 백준 16935번 배열 돌리기 3 (0) | 2023.11.23 |
[Python/파이썬] 백준 10703번 유성 (1) | 2023.10.21 |