WILDCARD 문제 질문입니다.

  • naegeora
    naegeora

    DP 로 풀었습니다.
    U=공백+"*p*" V=공백+"help" 로 놓고,
    U="*" 일때는 즉if(U.charAt(i)=='*')일 경우,
    D[i-1][j]==1, D[i-1][j-1]==1 인 경우 D[i][]=1;
    if((U.charAt(i)=='?')||(U.charAt(i)==V.charAt(j)))인 경우는
    if(D[i-1][j-1]==1)D[i][j]=1;로 했습니다.
    그리고 비교후 if(D[N-1][M-1]==1)pq.add(V.trim());하여
    Priority queue에 넣고 출력함.
    오답이 나오네요......이유를 잘 모르겠습니다.

    import java.io.FileInputStream;
    import java.util.PriorityQueue;
    import java.util.Scanner;

    public class Main {
    static int[][] D;
    static PriorityQueue pq=new PriorityQueue();
    public static void main(String[] args) throws Exception {
    Scanner sc = new Scanner(System.in);
    int T=sc.nextInt();
    for(int tcase=1;tcase<=T;tcase++){
    String U=" "+sc.next();
    int N=U.length();
    int C=sc.nextInt();
    for(int ccase=1;ccase<=C;ccase++){
    String V=" "+sc.next();
    int M=V.length();
    D=new int[N][M];
    D[0][0]=1;
    for(int i=1;i<N;i++){
    for(int j=1;j<M;j++){
    if(U.charAt(i)=='*'){
    if(D[i-1][j-1]==1||D[i-1][j]==1){
    for(int k=j;k<M;k++) D[i][k]=1;
    break;
    }
    }
    else if((U.charAt(i)=='?')||(U.charAt(i)==V.charAt(j))){
    if(D[i-1][j-1]==1)D[i][j]=1;
    }

    }
    
                }
                if(D[N-1][M-1]==1)pq.add(V.trim());
            }
        }
        while(!pq.isEmpty()){
            System.out.println(pq.poll());
        }
        sc.close();
    }

    }


    8년 전
1개의 댓글이 있습니다.
  • JongMan
    JongMan

    *를 처리하는 로직이 틀린 것 같은데 간단한 데이터를 많이 만들어서 테스트해보시는걸 추천드리겠습니다.


    8년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.