[BaekJoon] 1141 접두사 (java)

🔗 문제 링크

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

📝 문제 풀이 방법

이번 문제는 한 문장으로 문제를 표현하면 접두사가 되는 조합이 들어가지 않는 최대 크기의 부분집합을 찾는 문제이다.

문제를 풀기 앞서 입력 조건을 보도록 하자.
입력 조건은 문자열의 수(N)가 최대 50, 문자열의 길이(M)가 최대 50인 것을 확인할 수 있다.
입력 조건의 수들이 작은 것을 보아 각 문자열을 이중 반복문으로 순회해도 $O(N^2)$이고, 문자열을 비교할 때 역시 $O(M)$이므로 결국 $O(MN^2) = 125,000$회 이내인 것을 알 수 있습니다.

그래서 저는 문제를 이중 루프로 풀었으며 최대 크기의 부분집합을 만들기 위해 문자열의 길이가 가장 큰것부터 Set에 넣어가며 문제를 풀었습니다.

🚨 주의할 점
문제를 보면 중복된 값이 들어갈 수 있어서 HashSet을 이용하는게 좋습니다.

👨🏻‍💻 작성한 코드

import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;

public class Main {

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		String[] strArr = new String[n];
		
		for (int i=0; i<n; i++) {
			strArr[i] = br.readLine();
		}
		
		
		// 문자열 길이를 기준으로 내림차순으로 정렬
		Arrays.sort(strArr, new Comparator<String>() {
			public int compare(String s1, String s2) {
				return Integer.compare(s2.length(), s1.length());
			}
		});
		
		
		HashSet<String> set = new HashSet<>();
		for (String s1: strArr) {
			if (set.size() == 0) {
				set.add(s1);
				continue;
			}

			// set에 있는 문자열중에 s1을 포함하는게 있으면 추가X
			boolean available= true;
			for (String s2 : set) {
				if (s2.indexOf(s1) == 0) {
					available = false;
					break;
				}
			}
			if (available) {
				set.add(s1);
			}
		}
		
		System.out.println(set.size());
	}

}

📝 알아가면 좋은 코드

배열에 있는 문자열의 길이를 기준으로 Sort하는 코드이다.
이와 같이 Comparator를 새로 정의해서 Sort하는 방법을 알아가면 좋을 것 같다.

Arrays.sort(strArr, new Comparator<String>() {
	public int compare(String s1, String s2) {
		return Integer.compare(s2.length(), s1.length());
	}
});