[BOJ] 1235 학생번호 - JAVA

1. 문제

1235번: 학생 번호

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

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

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

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

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

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

---

2. 풀이

1.  Set을 이용했다.

2.  맨 뒤부터 한글자씩 늘려가면서 set에 넣은 후, 최종 set의 크기가 학생 수와 같다면 k를 출력하고 종료한다.

import java.io.*;
import java.util.*;

public class BOJ_1235_학생번호 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int N = Integer.parseInt(in.readLine());
      Set<String> set = new HashSet<>();

      String[] input = new String[N];
      for(int i=0;i<N;i++) input[i] = in.readLine();
      int len = input[0].length();

      for(int k=1;k<=len;k++){
         for(int i=0;i<N;i++){
            set.add(input[i].substring(len-k));
         }
         if(set.size()==N){
            System.out.println(k);
            return;
         }
         set.clear();
      }
   }
}

---

3. 결과