[백준] 학생 번호 1235

1. 문제 링크

 

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

 

문제

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

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

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

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

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

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

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

입력

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

출력

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

예제 입력

3
1212345
1212356
0033445

정답 : 3

 

2. 코드

let input = Int(readLine()!)!
var studentList : [String] = []
var result : Int = 0

for _ in 0..<input{
    let str = String(readLine()!)
    studentList.append(str)
}

let length = studentList[0].count   // 학생들의 학생 번호는 서로 다르지만 길이는 항상 같다

for i in (0..<length).reversed(){   // 0..<7을 반대로 6부터 0까지
    var temp = Set<String>()        // 자른 번호를 중복 처리 안되게끔
    for j in studentList{

        let startIndex = j.index(j.startIndex, offsetBy: i)     //시작 지점을 i로 한 이유는 i는 감소하기 때문에
        let endIndex = j.index(j.startIndex, offsetBy: length - 1)  // 끝나는 지점은 항상 6이기 때문에
        let subString = j[startIndex...endIndex]    //문자열 자르기
        temp.insert(String(subString))  // temp에 넣어 판단
    }
    if temp.count == studentList.count{     // 위에서 잘라서 넣은 문자열의 개수가 입력받은 학생 리스트 개수랑 같으면
        result = length - i     // 총 길이에서 현재 진행하고 있는 i의 값 빼기
        break
    }
}

print(result)

 

3. 코드 설명

입력받은 학생 번호를 studentList에 저장합니다.
temp라는 빈 Set을 생성합니다. Set은 순서대로 잘린 학생 번호를 저장하기 위한 용도입니다.

subString이 뒤에서부터 하나씩 증가하면서 잘린 번호입니다. 
학생 번호를 순서대로 반복하면서, 각 번호를 temp에 추가합니다.

for i in (0.. <length). reversed() 이쪽에서 반복을 돌면서 새로운 temp을 생성합니다.

 

temp에 있는 번호의 개수가 studentList의 길이와 같으면, 서로 다른 번호로 만들 수 있으므로 최소의 k를 찾았습니다.