[백준 - 자바] [실버] 1141.접두사

이번 주의 문제

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

접두사X 집합이란 집합의 어떤 한 단어가, 다른 단어의 접두어가 되지 않는 집합이다. 예를 들어, {hello}, {hello, goodbye, giant, hi}, 비어있는 집합은 모두 접두사X 집합이다. 하지만, {hello, hell}, {giant, gig, g}는 접두사X 집합이 아니다.

단어 N개로 이루어진 집합이 주어질 때, 접두사X 집합인 부분>집합의 최대 크기를 출력하시오.

<입력>
첫째 줄에 단어의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 단어가 주어진다. 단어는 알파벳 소문자로만 이루어져 있고, 길이는 최대 50이다. 집합에는 같은 단어가 두 번 이상 있을 수 있다.

생각해본 풀이

1. 일단 완전 탐색을 고민해봤다.하나의 단어를 잡고, 모든 단어를 돌며 검사해볼까?
2. 선택된 단어는 본인보다 길이가 짧은 단어의 접두사가 될 수 없다!
3. 그러면 단어의 길이에 맞춰 정렬한 후, 맞춰보면 될 것 같다.

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

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[] arr= new String[N];
		
		for(int n = 0; n < N; n++) {
			arr[n] = br.readLine();
		} //입력 완료
		
		Arrays.sort(arr, new Comparator<String>() {
			@Override
		    public int compare(String a, String b) {
		        // 문자열 길이를 기준으로 정렬
		        if (a.length() != b.length()) {
		            return a.length() - b.length(); // 길이가 짧은 순서로 정렬
		        }
		        
		        // 길이가 같으면 사전순 정렬
		        return a.compareTo(b);
		    }
		});
		
		int count = N;
		
		for(int i = 0; i < N; i++) {
			for(int j = i + 1; j < N; j++) {
				if(arr[j].startsWith(arr[i])) {
					count--;
					break;
				}
			}
		}
		
		System.out.println(count);
	}
}

함께 보면 좋은 알고리즘

그리디 알고리즘

최적의 값을 구하기 위해 최적이라고 생각되는 것을 선택하는 방식으로 진행되어 "탐욕법"이라고도 불린다. 그러나 항상 최적의 값을 보장하지는 않는다. 단기적 목표를 중심으로 전략적인 접근하는 방법이라고 보면 된다.

다이나믹 프로그래밍(동적 계획법)이나 백트래킹과 다른 점은, 현재 조건에서 선택을 했다면, 더이상 다른 선택 가능 경우는 검증하지 않는다. 따라서 잘못 접근하게 되면, 최적값을 구할 수 없다. 늘 조심해서 접근해야 한다.

해당 문제에서는 생각해본 순서 2번을 통해서("선택된 단어는 본인보다 길이가 짧은 단어의 접두사가 될 수 없다!") 단기 목표(나보다 같거나 긴 것만 보겠다)를 향해 나아가는 탐욕법이라고 볼 수 있다.