성능 요약
메모리: 14192 KB, 시간: 100 ms
분류
그리디 알고리즘, 정렬, 문자열
제출 일자
2024년 9월 12일 17:08:09
문제 설명
접두사X 집합이란 집합의 어떤 한 단어가, 다른 단어의 접두어가 되지 않는 집합이다. 예를 들어, {hello}, {hello, goodbye, giant, hi}, 비어있는 집합은 모두 접두사X 집합이다. 하지만, {hello, hell}, {giant, gig, g}는 접두사X 집합이 아니다.
단어 N개로 이루어진 집합이 주어질 때, 접두사X 집합인 부분집합의 최대 크기를 출력하시오.
입력
첫째 줄에 단어의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 단어가 주어진다. 단어는 알파벳 소문자로만 이루어져 있고, 길이는 최대 50이다. 집합에는 같은 단어가 두 번 이상 있을 수 있다.
출력
첫째 줄에 문제의 정답을 출력한다.
풀이(그리디 알고리즘)
문제 해결 방식은 어렵지 않게 알 수 있었다.
1. 문자열을 정렬한다. (크기가 제각각으로 입력되기 때문에)
2. 문자열을 서로 비교해 큰 문자열에 작은 문자열이 부분문자열이면서 첫 문자열에 나오는지 확인한다.
3. 맞다면 원래 단어 N개에서 하나를 줄이며,for문을 통해 계속 탐색한다.
이를 위해 우리는 문자열 정렬 (길이를 기준으로)과 문자열 함수인 startsWith 혹은 indexOf를 써야한다.
혹시 잘 모르겠다면 참고하자.
그런데 처음 풀이가 바로 틀렸습니다 가 나온 문제이다...
첫번째 풀이로도 충분히 가능할 것이라고 생각했는데 당황했다.
첫번째 풀이 (실패)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Set;
public class Main {
//그리디 알고리즘 문제
static Set<String> banWord = new HashSet<>();
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
String[] words = new String[N];
for(int i=0; i<N; i++) {
words[i] = br.readLine();
}
//문자열 내림차순 정렬하기
Arrays.sort(words,new Comparator<String>() {
@Override
public int compare(String str1, String str2) {
return str2.length()-str1.length();
}
});
int result=N;
for(int i=0; i<N; i++) {
for(int j=i+1; j<N; j++) {
System.out.println("순서: "+words[i]+" "+words[j]);
//문자열 비교하기 -> 부분 문자열인지 확인 && 문자열내 첫 문자열이 겹치는지 확인
if(words[i].contains(words[j])) {
if(words[i].startsWith(words[j])) {
if(banWord.contains(words[j])) {
//이미 집합에 넣지 않을 문자라면 고려 X
continue;
}
else {
//집합에 넣지 않을 문자열 추가
banWord.add(words[j]);
result--;
}
}
}
}
}
//최대 집합 크기
System.out.println(result);
}
}
먼저 위 풀이에서 실수한 점은 바로 contains와 startsWith를 같이 썼다는 점이다.
startsWith는 부분문자열이 첫 시작 문자열에 나오는 지 확인하는데,
contains는 부분문자열이 문자열에 포함되는 지만 확인하는 함수다.
즉 startsWith를 쓰면 굳이 contains를 쓸 필요가 없다.
하지만 그렇다고 해서 문제가 될 이유는 없다. 포함하는 지 확인한 후, 첫 문자열에 해당하는 지 확인한다고 해서 크게 문제가 될 것은 없다고 생각한다.
중복 처리 관련 문제인가 싶었지만, Set을 통해 안되는 문자열을 지워나갔기에 이 또한 아니라고 본다.
아직 어디서 틀린건지 정확히 모르겠어서 이 부분은 더 공부가 필요할듯하다...
혹시나 어느 부분에서 잘못됐는 지 알겠다면 댓글 부탁드립니다
두번째 풀이 (성공)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Set;
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[] words = new String[N];
for(int i=0; i<N; i++) {
words[i] = br.readLine();
}
//문자열 내림차순 정렬하기
Arrays.sort(words,new Comparator<String>() {
@Override
public int compare(String str1, String str2) {
return str1.length()-str2.length();
}
});
int result=N;
//만약 문자열이 접두사형태면 하나씩 지워간다.
for(int i=0; i<N; i++) {
for(int j=i+1; j<N; j++) {
if(words[j].startsWith(words[i])) {
result--;
break;
}
}
}
//최대 접두사 X 집합 크기
System.out.println(result);
}
}결국 다른 블로그 풀이를 참고했다. 내가 처음 짰던 풀이와 어느 정도 비슷해 이해하고 적용하기 어렵지 않아 채택했다.
[해당 블로그]
