-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
4-F 시간복잡도 O(2^26) 이면 풀려야 하는 것 아닌가요? ㅠㅠ
23.04.05 22:18 작성 조회수 2.95k
0
자바가 느려서인지, 아니면 제가 첨부터 접근을 잘못한건지 모르겠습니다. ㅠㅠ
package lecture4;
import java.util.*;
public class Prob1062 {
static List<Set<Character>> sets = new ArrayList<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
if(k<5){
System.out.println(0);
return;
}else if (k==26){
System.out.println(n);
return;
}
List<String> list = new ArrayList<>();
for (int i = 0; i < n; i++) { // 문자열 입력 받기
String str = sc.next();
list.add(str);
Set<Character> set = new HashSet<>(); // 각 문자열의 문자들을 Set에 저장.
for (char c : str.toCharArray()) {
set.add(c);
}
sets.add(set);
}
List<Set<Character>> filtered = new ArrayList<>();
for (int i = 0; i < n; i++) { // K 보다 많은 알파벳으로 이루어진 경우 제외
if(sets.get(i).size()<=k){
filtered.add(sets.get(i));
}
}
List<Integer> masks = new ArrayList<>();
for (Set<Character> set : filtered) { // Set의 각 알파벳을 대응되는 비트마스크로 표현
masks.add(setToMask(set));
}
int mask = 1;
int max = 0;
while (mask < (1<<26)-1){ // 모든 경우의 수 탐색
if(Integer.bitCount(mask)>k){ // 비트마스크의 1 개수가 k 보다 크면 다음 경우로 넘어가기
mask++;
continue;
}
int count = 0;
for (Integer m : masks) { // 문자열을 비트마스크로 표현한 것을 비교해서 읽을 수 있는건지 개수 샘
if((mask & m) == m){
count++;
}
}
max = Math.max(max,count); // 최대값 저장
mask++;
}
System.out.println(max);
}
private static int setToMask(Set<Character> set){
int[] num = new int[26];
for (Character character : set) {
num[25 - (character-'a')] = 1;
}
StringBuffer sb = new StringBuffer();
for (int i : num) {
sb.append(i);
}
return Integer.parseInt(sb.toString(),2);
}
}
답변을 작성해보세요.
0
큰돌
지식공유자2023.04.06
안녕하세요 ㅎㅎ
작성자가 삭제된 글은 처음보네요.. ㅎㅎ
죄송하지만 C++로만 QA를 받고 있습니다. C++로 포팅해서 질문주세요. ㅎㅎ
감사합니다.
답변 1