[BOJ] 1141 - 접두사 (Java)

알고리즘

• 그리디 알고리즘
• 문자열
• 정렬

1. 문제

2. Idea

• 문자열 길이 기준 오름차순으로 정렬 후 길이가 가장 작은 순서로 확인

3. 풀이

3.1. 변수 선언 및 초기화

• n : 입력받을 문자열의 수
• strArr[] : 입력된 문자열을 저장할 배열

int n = Integer.parseInt(sc.nextLine());
String[] strArr = new String[n];

3.2. 배열에 문자열 저장

for (int i=0; i<n; i++) {
	strArr[i] = sc.nextLine();
}

3.3. 문자열 길이를 기준으로 내림차순으로 정렬

Arrays.sort(strArr, (s1, s2) -> Integer.compare(s2.length(), s1.length()));

3.4. 접두사 여부 및 중복 요소 확인

• 중복 요소 저장 방지를 위한 HashSet 생성
• 길이를 기준으로 정렬된 배열의 요소를 하나씩 꺼냄
• HashSet에 size가 0인 경우 add (문자열의 길이가 가장 짧은 것은 무조건 접두사 집합에 포함)
• boolean available : 문자열 s1을 HashSet set에 추가할 수 있는지 여부
• HashSet에 이미 존재하는 문자열들을 순회하면서 현재의 s1이 다른 문자열의 접두사가 되지 않는지 확인
• 만약 다른 문자열의 접두사라면 available을 false로 설정 후 break (접두사가 겹치므로, HashSet에 추가할 수 없는 경우)
• HashSet을 모두 확인했을 때, available == true이면 현재의 s1을 HashSet에 추가

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); }
	}

3.5. 결과 출력

• HashSet의 크기 출력

System.out.println(set.size());

4. 전체코드

package week5;
//Silver_접두사
import java.util.*;
public class BOJ_1141 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = Integer.parseInt(sc.nextLine());
        String[] strArr = new String[n];

        for (int i=0; i<n; i++) {
            strArr[i] = sc.nextLine();
        }
        
        // 문자열 길이를 기준으로 내림차순으로 정렬
        Arrays.sort(strArr, (s1, s2) -> 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());
    }
}