2022.03.09 74일차

백준 1141번 (접두사)

문제

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

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

나의 풀이

1. 각 단어를 다른 단어의 앞부분과 비교
2. 중복 없애기 위해 set 사용
3. 이중 for문 사용, 두 인덱스 같으면 생략
4. 바깥 인덱스의 값(비교 대상, temp1)의 길이가 안쪽보다 짧을 때만 비교
5. 안쪽 값(temp2)에 substring을 적용(temp3), temp1과 비교
6. 같으면 조건 불충족, 조건 통과하면 카운트 증가

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Set<String> set = new HashSet<>();

        int N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {
            String temp = br.readLine();
            set.add(temp);
        }

        String[] setArr = new String[set.size()];
        
        int count = 0;
        for (String s : set) {
            setArr[count] = s;
            count++;
        }

        int answer = 0;

        for (int i = 0; i < setArr.length; i++) {
            String temp1 = setArr[i];
            boolean cond1 = true;

            for (int j = 0; j < setArr.length; j++) {
                if (i == j) continue;

                String temp2 = setArr[j];

                if (temp1.length() < temp2.length()) {
                    String temp3 = temp2.substring(0, temp1.length());

                    if (temp3.equals(temp1)) {
                        cond1 = false;
                        break;
                    }
                }
            }

            if (cond1) {
                answer++;
            }
        }

        System.out.println(answer);
    }
}

생각하기

• Set -> 배열
  배열의 크기를 0으로 지정하면 자동으로 배열 크기 지정

String[] setArr = set.toArray(new String[0]);

• Set 활용안하고도 풀이 가능