jlis 문제 오답 이유를 잘 모르겠는데 오답나는 인풋이 어떤경우가 있을까요

  • gugama
    gugama

    제가 처리한 로직은 이렇습니다.

    인풋을 두 배열에 나누어받고
    reducer라는 메소드에서 각 배열을 부분증가수열들로 나눕니다.

    만약 [5,6,7,3,4,9,10]이 들어왔다면
    [[5,6,7,9,10],[3,4,9,10]]으로 나누도록 하였습니다.

    그리고 만들어진 두개의 부분증가수열의 배열을
    이중 루프문으로 돌면서
    중복을 배제한 set을 만들고
    set의 사이즈가 최대가 되는 경우를 리턴하도록 하였습니다.

    책에 주어진 인풋으로 테스트했을땐 정확히 돌아가고
    임의로 작성해본 몇몇 인풋에 대해서도 정상작동하는데

    알고스팟에서는 '오답'으로 나와서 어떤부분에서 잘못되었는지
    혹은 반증하는 인풋이 있다면 어떤것인지 알고싶습니다.

    소스코드를 첨부합니다

    import java.util.ArrayList;
    import java.util.HashSet;
    import java.util.Scanner;
    import java.util.Set;
    
    public class Main {
        public static void main(String[] args){
            int size1=0;
            int size2=0;
            ArrayList<Integer> subsq1;
            ArrayList<Integer> subsq2;
            Scanner sc=new Scanner(System.in);
            int caseNum=sc.nextInt();
            sc.nextLine();
            while(caseNum>0){
                size1=sc.nextInt();
                size2=sc.nextInt();
                sc.nextLine();
                subsq1=new ArrayList<Integer>();
                subsq2=new ArrayList<Integer>();
                while(size1>0){
                    subsq1.add(sc.nextInt());
                    size1--;
                }
                sc.nextLine();
                while(size2>0){
                    subsq2.add(sc.nextInt());
                    size2--;
                }
                solver(subsq1,subsq2);          
                caseNum--;
            }
            return;
        }
        public static void solver(ArrayList<Integer> subsq1,ArrayList<Integer> subsq2){
            int result=0;
            ArrayList<ArrayList<Integer>> tokenized1=reducer(subsq1);
            ArrayList<ArrayList<Integer>> tokenized2=reducer(subsq2);
            Set<Integer> buffer=new HashSet<Integer>();
            for(int i=0;i<tokenized1.size();i++){
                for(int j=0;j<tokenized2.size();j++){
                    buffer.clear();
                    buffer=insertBuffer(buffer,tokenized1.get(i));
                    buffer=insertBuffer(buffer,tokenized2.get(j));
                    if(buffer.size()>result)
                        result=buffer.size();
                }
            }
            System.out.println(result);
        }
        public static ArrayList<ArrayList<Integer>> reducer(ArrayList<Integer> subsq1){
            ArrayList<ArrayList<Integer>> tokenized1=new ArrayList<ArrayList<Integer>>();
            int index1=0;
            for(int i=0,j=0;i<subsq1.size()-1;i++){
                if(subsq1.get(i)>subsq1.get(i+1)){
                    tokenized1.add(new ArrayList<Integer>());
                    for(int k=j;k<subsq1.size();k++){
                        if(subsq1.get(j)>subsq1.get(k))
                            continue;
                        tokenized1.get(index1).add(subsq1.get(k));
                    }
                    j=i+1;
                    index1++;
                }
                if(i==subsq1.size()-2){
                    tokenized1.add(new ArrayList<Integer>());
                    for(int k=j;k<subsq1.size();k++){
                        tokenized1.get(index1).add(subsq1.get(k));
                    }
                }
            }
            return tokenized1;
        }
        public static Set<Integer> insertBuffer(Set<Integer> buffer,ArrayList<Integer> subsq1){
            for(int i=0;i<subsq1.size();i++){
                buffer.add(subsq1.get(i));
            }
            return buffer;
        }
    }
    

    11년 전
5개의 댓글이 있습니다.
  • JongMan
    JongMan

    배열을 어떻게 부분 증가 수열로 나누나요? @_@


    11년 전 link
  • JongMan
    JongMan

    하여간 두 배열이 주어질 때, 각 배열에서 증가 수열을 각각 적절히 구한 뒤 이들을 합치면 최적해를 구할 수 있다는 가정을 갖고 계신 것 같은데 이게 참이 아닐 수도 있는듯합니다. 정확하게 어떻게 나누시는지 몰라서 뭐라 할 순 없지만요.


    11년 전 link
  • gugama
    gugama

    예를들어서 [1,2,4,3,8,9]를 인풋으로 넣을경우
    [[1,2,4,8,9],[3,8,9]] 를 반환하고
    [4,7,10,11,1,2]를 넣을경우
    [[4,7,10,11],[1,2]]를 반환하도록 하여서
    4가지 경우의 수를 탐색해서 (Set이용)
    사이즈가 가장 큰 경우를 반환하도록 하였습니다

    혹시 짐작가는 오류부분이 있으시면 언급해주시면 감사하겠습니다


    11년 전 link
  • Being
    Being

    음 그러니까 논점은, 어떻게 하나의 배열을 두 개의 부분 증가 수열로 적절히 계산했는지 불분명해서 답변을 드리기 곤란하다는 뜻입니다. 설명해주신 건 알고리즘에 대한 설명이 아니고 마치 예제 입/출력과 같이 어떤 입력을 넣으면 어떤 출력이 나오는 알고리즘입니다 라는 예시만 제시해 주셨고요, 소스 코드를 붙여 주셨으나 가능하면 글쓰기 방법을 참조하여 하이라이트를 해 주셔야 저 뿐만이 아니라 다른 분들이 답변해 드리기 용이할 것 같습니다.

    그와 별개로 아마 그런 방식으로는 답을 구하지 못하리라는 90% 이상의 확신이 있는데, 정확히 무슨 방식으로 하셨는 지 모르겠어서 콕 꼬집어 설명드리기 곤란하네요 (JongMan 님의 말씀과 같은 뜻입니다)


    11년 전 link
  • astein
    astein

    (편의상 소스코드를 알아보기 쉽게 본문을 조금 수정하였습니다.)

    코드에서 reducer() 함수가 잘못 구현되어 있습니다. [3,2,1,4,5] 같은 데이터에서 [3,4,5],[2,4,5][1,4,5]의 세 가지 수열을 만들 수 있는데 위의 코드에서는 올바른 리턴이 나오지 않을 것 같네요.

    그리고 위와 같은 방법대로 구현한다면 [2,1,4,3,6,5,8,7,...,] 과 같은 배열이 입력으로 주어졌을 때, 총 원소의 수가 N이면 2^(N/2) 개의 SET이 생성될 것으로 보입니다.


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