백준 30805 사전 순 최대 공통 부분 수열 (java)

https://www.acmicpc.net/problem/30805

수열 둘의 최대길이가 100자리다. 시간제한이 1초인 문제이기에 수열을 하나하나 확인하고 있으면 시간초과가 난다.

100자리 수열의 부분수열을 모두 구하려면 2^100회나 비교해보아야 하기 때문에 불가능.

백트래킹으로 했었다가 시간 초과로 틀렸다. 아래는 틀렸던 코드.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.*;

public class Main {
    static int an,bn;
    static char[] arrA = new char[101]; static char[] arrB = new char[101];
    static String resultStr= "";
    static void backtracking(String str,int startidx){
        //System.out.println(str);
        int count=0;
        int idx=0;
        for(int i=0;i<str.length();i++){
            int check=0;
            for(int j=idx;j<an;j++){
                if(str.charAt(i)==arrA[j]){
                    count++;
                    idx=j++;
                    check++;
                    break;
                }
            }
            if(check==0) return;
        }

        if(str.compareTo(resultStr)>0){
            resultStr=str;
        }

        for(int i=startidx;i<bn;i++){
            backtracking(str+arrB[i],i+1);
        }
        /*
        ""
        bt(a,1);
        a
        bt(ab,2);
        ab
        bt(abc,3);
         */
    }


    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        an=Integer.parseInt(br.readLine());
        String str= br.readLine();
        StringTokenizer token = new StringTokenizer(str);
        for(int i=0;i<an;i++){
            arrA[i]=(token.nextToken().charAt(0));
        }
        bn=Integer.parseInt(br.readLine());
        str= br.readLine();
        token = new StringTokenizer(str);
        for(int i=0;i<bn;i++){
            arrB[i]=(token.nextToken().charAt(0));
        }
        backtracking("",0);

        bw.write(resultStr.length()+"\n");
        for(int i=0;i<resultStr.length();i++){
            bw.write(resultStr.charAt(i)+" ");
        }

        bw.flush();
        bw.close();
    }
}

 

사전순으로 가장 뒤인 수열은 수열의 첫자리가 다른 수열보다 크거나 같아야한다.

두 수열 모두에 공통으로있는 가장 큰 수를 시작으로 해서 기존 수열의 순서를 신경쓰며

가장 큰 수를 하나씩 결과 수열에 추가하면 되는 그리디 문제였다.

 

1. a.compareTo(b)의 경우, a가 사전순으로 뒤에 있거나 더 크면 양수를 반환한다.

2.입력 예시가 한자릿수였기에 결과 수열을 문자열에 추가해서 한자리씩 출력해버렸는데

100이하의 수가 조건이었다. 이런 부분 꼼꼼하게 확인.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.*;

public class Main {
    /*

     */
    static int an,bn;

    static ArrayList<Integer> arrA = new ArrayList<>();
    static ArrayList<Integer> arrB = new ArrayList<>();
    static ArrayList<Integer> resultarr = new ArrayList<>();

    static void solve(int astart,int bstart){
            if(astart>=arrA.size()){
                return;
            }
            int max=Integer.MIN_VALUE;
            int aidx=astart,bidx=bstart;
            int amax=astart;
            for(int i=astart;i<arrA.size();i++){
                if(arrA.get(i)>max){
                    max=arrA.get(i);
                    amax=i;
                }
            }
            for(int j=bstart;j<arrB.size();j++){
                if(arrB.get(j)==max){
                    resultarr.add(arrB.get(j));
                    arrB.remove(j);
                    bidx=j;
                    aidx=amax;
                    break;
                }
            }
            arrA.remove(amax);
            solve(aidx,bidx);
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        an=Integer.parseInt(br.readLine());
        String str= br.readLine();
        StringTokenizer token = new StringTokenizer(str);
        for(int i=0;i<an;i++){
            arrA.add(Integer.parseInt(token.nextToken()));
        }
        bn=Integer.parseInt(br.readLine());
        str= br.readLine();
        token = new StringTokenizer(str);
        for(int i=0;i<bn;i++){
            arrB.add(Integer.parseInt(token.nextToken()));
        }
        solve(0,0);

        bw.write(resultarr.size()+"\n");
        for(int i=0;i<resultarr.size();i++){
            bw.write(resultarr.get(i)+" ");
        }

        bw.flush();
        bw.close();
    }
}