[Baekjoon] 1141_접두사

Silver I

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

---

< 접두사 >

 

문제 풀이 

 

접두사 X집합인 부분집합의 최대 크기를 구하기 위해서는 한 단어가 다른 단어의 접두어가 되는 단어를 하나씩 빼면 된다고 생각하고 문제를 해결했다. 예를 들어 [h, hi, hello]가 있다면 h가 hi의 접두어 이므로 제외하고 hi는 hello의 접두어가 아니므로 [h], [hi, hello]로 나누면 부분 집합의 최대 크기인 2를 구할 수 있다. 

 

 

 my solution (Java)

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

public class _1141_ { // 접두사

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

		int n = Integer.parseInt(bf.readLine());

		String arr[] = new String[n];
		for (int i = 0; i < n; i++) {
			arr[i] = bf.readLine();
		}

		Arrays.sort(arr);

		int result = 0;
		boolean flag = false;

		for (int i = 0; i < n - 1; i++) {
			flag = false;
			for (int j = 0; j < arr[i].length(); j++) {
				if (arr[i].charAt(j) != arr[i + 1].charAt(j)) {
					flag = true;
				}
				if (flag) {
					break;
				}
			}
			if (!flag) {
				result += 1;
			}
		}
		System.out.println(n - result);
	}
}

 

Main

변수)
n : 단어의 개수
arr : 단어 저장 배열
result : 다른 단어의 접두어인 단어 개수
flag : 일치 여부

 

단어의 개수(n)를 입력받은 후 단어의 개수만큼 단어를 입력받아 배열에 저장한다.

한 단어가 다른 단어의 접두어가 되는지 확인하기 위해서는 비슷한 단어끼리 확인해야 하므로 정렬해 준다.

정렬한 배열을 순환하며 인접한 단어의(=다음 단어의) 접두어인지 확인한다. 접두어라면 result +1을 해준다. 

최종 출력해야 하는 접두사 X 집합인 부분집합의 최대 크기는 (전체 단어의 개수) - (다른 단어의 접두어인 경우)이다.  

 

---

---