[BaekJoon] 1235 학생 번호

1.  문제 링크

2.  문제

요약

• 각 학생에게 같은 길이의 고유 번호를 부여했는데, 고유 번호의 길이가 길어 고유 번호를 뒤에서부터 모든 학생의 번호를 같은 길이로 자를 예정입니다.
• 자를 때, 모든 학생을 구분할 수 있는 고유 번호로서 역할을 할 수 있는 번호의 길이의 최소값을 구합니다.
• 입력: 첫 줄에는 학생의 수가 주어지고 다음 줄부터는 각 학생의 고유 번호가 주어집니다.
• 출력: 길이의 최소값을 출력합니다.

3.  소스코드

초기 버전

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {
	public int find(ArrayList<String> reverse_num) {
		int count = 1;
		while(true) {
			ArrayList<String> identifier = new ArrayList<String>();
			for(int i = 0; i < reverse_num.size(); i++) {
				String temp = "";
				for(int j = 0; j < count; j++) {
					temp += reverse_num.get(i).substring(j, j + 1);	
				}
				identifier.add(temp);
			}
			boolean flag = true;
			for(int i = 0; i < identifier.size() - 1; i++) {
				for(int j = i + 1; j < identifier.size(); j++) {
					if(identifier.get(i).equals(identifier.get(j))) {
						flag = false;
						break;
					}
				}
				if(!flag)
					break;
			}
			if(flag)
				break;
			count++;
		}
		return count;
	}
	
	public int findIdentifier(ArrayList<String> stu_nums) {
		ArrayList<String> reverse_num = new ArrayList<String>();
		for(int i = 0; i < stu_nums.size(); i++) {
			String num = "";
			for(int j = stu_nums.get(i).length(); j > 0; j--) {
				num += stu_nums.get(i).substring(j - 1, j);
			}
			reverse_num.add(num);
		}
		int result = find(reverse_num);
		return result;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int num = Integer.parseInt(br.readLine());
		ArrayList<String> stu_nums = new ArrayList<String>();
		for(int i = 0; i < num; i++) {
			stu_nums.add(br.readLine());
		}
		Main m = new Main();
		System.out.println(m.findIdentifier(stu_nums));
	}
}

수정된 버전

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

public class Main {
	public int findIdentifier(ArrayList<String> stu_nums) {
		int total_length = stu_nums.get(0).length();
		int length = total_length - 1;
		while(true) {
			Set identifier = new HashSet();
			for(int i = 0; i < stu_nums.size(); i++) {
				identifier.add(stu_nums.get(i).substring(length, total_length));
			}
			if(identifier.size() == stu_nums.size()) {
				break;
			}
			length--;
		}
		return total_length - length;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int num = Integer.parseInt(br.readLine());
		ArrayList<String> stu_nums = new ArrayList<String>();
		for(int i = 0; i < num; i++) {
			stu_nums.add(br.readLine());
		}
		Main m = new Main();
		System.out.println(m.findIdentifier(stu_nums));
	}
}

4.  접근

• 가장 뒤에서부터 길이를 늘려가면서 가장 먼저 모든 숫자가 달라질 때의 길이가 최소값이 될 것입니다.
• 초기 버전에서는 주어진 번호를 뒤집은 후에 앞에서부터 확인을 하였고, 길이를 하나씩 늘려가면서 각 학생들의 잘려진 고유 번호를 구한 후에 각 숫자가 같은지 확인을 하여 가장 먼저 달라질 때의 길이를 출력하였습니다.
• 초기 버전은 기능별로 함수로 나누어 두었지만, 2중 for문이 많이 쓰이며 시간 복잡도가 많이 늘어났습니다.
• 수정된 버전에서는 중복되는 객체가 여러 번 저장되지 않는 HashSet을 이용하였습니다.
• 수정된 버전에서는 주어진 번호를 뒤집어 앞에서부터 확인을 하는 과정이 불필요하다 생각하여 제거하였고 길이를 늘려가며 잘려진 고유 번호들을 HashSet에 저장하였습니다.
• 학생의 수와 HashSet에 저장이 된 객체의 수가 같다면 중복된 것이 없이 모두 저장이 되었다는 의미이므로 가장 먼저 수가 같아졌을 때의 길이를 출력하였습니다.