BOJ_1235 : 학생 번호

👉 문제링크

1235번: 학생 번호

---

---

🔸 문제 분석 🔸

• 학생번호를 중복되지 않도록 가장 짧게 만들 수 있는 길이를 출력한다.
  • 번호를 줄일때는 왼쪽수 부터 버린다.

🔸 문제 풀이 🔸

• 학생 번호 문자열의 끝 부분에서 하나씩 길이를 늘려가며 중복되는 문자열이 있는지 확인해야한다.
  • 끝 부분에 있으면 접근이 어려울 것 같아 문자열을 뒤집어서 저장 후 중복을 확인했다.
  • 중복확인을 위해 문자열을 1부터 N-1까지 잘라가며 Set에 넣고 확인했다.

🔸 코드 🔸

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

public class Main {
	public static void main(String[] args) throws IOException {
		// Input
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int N = Integer.parseInt(br.readLine());

		String[] students = new String[N];

		for (int i = 0; i < N; i++) {
			StringBuilder sb = new StringBuilder(br.readLine());
			students[i] = sb.reverse().toString();
		}

		// Process
		int i = 0;
		int length = students[0].length() - 1;

		for (i = 0; i < length; i++) {
			boolean flag = true;
			Set<String> set = new HashSet<>();
			for (int j = 0; j < N; j++) {
				String s = students[j].substring(0, i + 1);
				if (set.contains(s)) {
					flag = false;
					break;
				}
				set.add(s);
			}
			if (flag)
				break;
		}

		// Output
		bw.write(Integer.toString(i + 1));
		bw.flush();
	}
}

🔸 코드 해석 🔸

• StringBuilder의 reverse()를 이용해 문자열을 뒤집어 저장했다.
• 문자열을 1부터 N-1 크기까지 잘라서 Set에 넣어보고 중복을 확인한다.
  • 문제에서 N길이는 이미 중복되지 않는다는 가정이 있기 때문에 N-1까지만 확인한다. 
  • 중복되면 다음 길이로 다시 확인한다.
  • 전부 중복되지 않으면 현재 길이를 출력한다.

---

🔸 end 🔸

• 문자열들을 정렬해서 같은 인덱스만 확인하면 되지 않을까 생각했지만, 첫 번째 인덱스만 해당되고 그 다음부터는 의미가 없던 계산이었다.
• 결국 substring과 Set을 통해 잘라가며 중복확인으로 풀이할 수 있었다.