[Baekjoon] 4865_Shortest Prefixes

문제(출처: https://www.acmicpc.net/problem/4865)

---

< Shortest Prefixes >

 

문제 풀이 

 

모든 단어를 substring을 이용해 잘라 접두사로 사용할 수 있는지 확인한다.

 

my solution (Java)

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

public class _4865_ { // Shortest Prefixes

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

		String str = "";

		ArrayList<String> list = new ArrayList<>();

		while ((str = bf.readLine()) != null) {
			list.add(str);
		}

		ArrayList<String> result = new ArrayList<>();
		for (int i = 0; i < list.size(); i++) {
			for (int j = 1; j <= list.get(i).length(); j++) {
				String temp = list.get(i).substring(0, j);
				boolean flag = false;

				for (int k = 0; k < list.size(); k++) {
					if (i == k) {
						continue;
					}
					if (list.get(k).startsWith(temp)) {
						flag = true;
						break;
					}
				}
				if (!flag) {
					result.add(temp);
					break;
				}
			}
			if (result.size() < (i + 1)) {
				result.add(list.get(i));
			}
		}

		for (int i = 0; i < list.size(); i++) {
			bw.write(list.get(i) + " " + result.get(i) + "\n");
		}
		bw.flush();
	}
}

변수)
str : 단어
list : 단어를 저장하는 ArrayList
result : 접두사를 저장하는 ArrayList
temp : 접두사
flag : 고유하게 식별하는 접두사 여부 

 

입력이 없을 때까지 단어를 입력받아 ArrayList에 저장한다. ArrayList를 탐색하면서 다음 과정을 거친다.

 

1) 단어 길이만큼 탐색하며 substring을 사용해 자르기

2) ArrayList를 탐색하며 접두사가 고유한지 확인

3) 고유하다면 접두사를 저장하는 ArrayList에 저장

4) substring을 사용해 모든 접두사를 찾았지만 고유한 값이 없다면 단어 자체를 접두사로 저장

 

최종 단어를 저장하는 ArrayList와 접두사를 저장한 ArrayList를 출력한다.

---

---