[백준] | JAVA, 자바 | 1235번 - 학생 번호

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

1235번: 학생 번호

---

문제 요약 :

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

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

 

( 첫째 줄에 구하고자 하는 가장 작은 k값을 출력 )

---

문제 풀이 :

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] student = new String[n];

        for (int i = 0; i < n; i++) {
            student[i] = br.readLine();
        }

        int start = 0;
        int end = student[0].length();
        int result = end;

        while (start <= end) {
            int mid = (start + end) / 2;
            if (isUnique(student, mid)) {
                end = mid - 1;
                result = mid;
            } else {
                start = mid + 1;
            }
        }
        System.out.println(result);
    }

    private static boolean isUnique(String[] student, int k) {
        Set<String> set = new HashSet<>();

        for (String s : student) {
            String cut = s.substring(s.length() - k);
            if (!set.add(cut)) {
                return false;
            }
        }
        return true;
    }
}

 

1. 학생의 수 n 입력받기

2. 입력받은 학생의 수만큼 학생 번호 입력받기

3. 이진 탐색을 사용하기 위해 시작점과 끝점, 최종 결과값을 담을 변수 생성

4. while문 실행, int mid를 통해 중간값을 계산

5. boolean isUnique를 통해 중복이 있는지 확인

5 - 1. 중복을 확인하기 위해 HashSet을 사용

5 - 2. 뒤에서 k 자리만 추려서 문자열에 저장

5 - 3. 만약 중복된 값이 존재해 HashSet에 추가가 안된다면 false를 리턴

5 - 4. 중복이 없다면 true를 리턴

6. 중복이 없다면 뒷부분을 더 줄일 수 있는지 확인하기 위해 end 값을 mid - 1로 저장, result에 mid 값 저장

7. 중복 값이 있다면 뒷부분을 늘림

8. start 값이 end 값보다 커진다면 while문 종료

9. 저장된 result 값 출력