백준 1235번 JAVA 풀이 - 학생번호

문제 링크 : https://www.acmicpc.net/problem/1235

1235번: 학생 번호

문제

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

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

이름번호

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

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

이름번호

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

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

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

입력

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

출력

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

 

# 문제 풀이

각 학생들의 학생 번호를 한글자씩 짤라 hashset에 넣는다. 

hashset의 크기가 입력받은 n과 같다면 그때 짜른 글자수를 출력하면 된다.

 

hashset은 equals() 메소드를 사용하여 동일한 값이 들어오면 저장하지 않는다. 따라서 hashset의 크기와 입력받은 n과 같다면 모두 다른 값이 들어왔다라는 의미이기 때문에 조건에 성립한다.

 

1. 학생들의 학번을 입력받을 String 배열을 만들어준다.

String[] arr = new String[n];

for(int i = 0; i < arr.length; i++){
	arr[i] = sc.next();
}

 

 

2. 번호를 짤라 넣을 HashSet을 만든다.

HashSet<String> temp = new HashSet<>();

 

 

3. 반복문을 통해 한글짜씩 짤라가며 비교한다.

for(int j = 0; j < n; j++){
	temp.add(arr[j].substring(arr[0].length() - i));
}

 

 

4. HashSet의 사이즈와 입력받은 n(학생수) 가 같다면 자른 글자수를 출력한다.

if(temp.size() == n){
	System.out.println(i);
	return;
}

 

 

# 전체 코드

import java.util.*;

public class Main_1235{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        String[] arr = new String[n];

        for(int i = 0; i < arr.length; i++){
            arr[i] = sc.next();
        }

        HashSet<String> temp = new HashSet<>();

        for(int i = 1; i <= arr[0].length(); i++){
            for(int j = 0; j < n; j++){
                temp.add(arr[j].substring(arr[0].length() - i));
            }
            if(temp.size() == n){
                System.out.println(i);
                return;
            }
            temp.clear();
        }
    }
}