RESTORE 구현이 왜 틀린지 모르겠습니다

  • ㅎㅅㅎ
    ㅎㅅㅎ

    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    import java.util.Scanner;

    public class RESTORE {

    private static final Scanner scanner = new Scanner(System.in);
    
    public static boolean check(String f, String e, int s) {
        String sub = e.substring(0, s);
        return f.contains(sub);
    }
    
    public static String concat(String f, String e) {
        int size = Integer.min(f.length(), e.length());
    
        int result = 0;
        for(int i=1; i<=size; i++) {
            if(check(f, e, i)) {
                result = i;
            }
        }
    
        return f + e.substring(result);
    }
    
    public static String solution(List<String> subs, List<Integer> indexes, String[] cache) {
        if(indexes.size() == 1) {
            return subs.get(indexes.get(0));
        }
    
        int cacheIndex = merge(indexes);
        if(cache[cacheIndex] != null) {
            return cache[cacheIndex];
        }
    
        int size = indexes.size();
        int minSize = Integer.MAX_VALUE;
        String result = "";
        for(int i=0; i<size; i++) {
            int index = indexes.remove(i);
            String sub = solution(subs, indexes, cache);
            String concated = concat(subs.get(index), sub);
            if(concated.length() < minSize) {
                result = concated;
                minSize = result.length();
            }
            indexes.add(i, index);
        }
    
        cache[cacheIndex] = result;
    
        return result;
    }
    
    public static int merge(List<Integer> indexes) {
        int result = 0;
        for(int index : indexes) {
            result = result + (1 << index);
        }
        return result;
    }
    
    public static void main(String[] args) {
        int C = scanner.nextInt();
        while(C-->0) {
            int k = scanner.nextInt();
            scanner.nextLine();
            List<String> subs = new ArrayList<>(k);
            List<Integer> indexes = new ArrayList<>(k);
            for(int i=0; i<k; i++) {
                subs.add(scanner.nextLine());
                indexes.add(i);
            }
    
            int size = 1 << k;
            String[] cache = new String[size];
    
    
            String result = solution(subs, indexes, cache);
            System.out.println(result);
    
        }
    }

    }

    구현에서는 길이를 미리 구해놓고 나중에 reconstruct하는데
    해당 방법말고 처음부터 캐시에 문자열을 저장하는 방법으로 접근해봤는데
    오답이라고 나옵니다.

    테스트 케이스는 잘 작동하는데 어디에서 예외인 건지 감을 못잡겠네요
    도움 부탁드립니다


    3주 전
0개의 댓글이 있습니다.
  • 댓글을 남기시려면 로그인하세요.