Sorting Game 시간 초과 질문

  • skghtjr2
    skghtjr2

    교재를 참고하여 코드를 작성하였습니다. 답안을 제출하면 시간 초과가 나오고 있습니다. 일단 테스트케이스 받기전에 너비탐색을 통해 모든 순열에 대한 연산의 수를 계산한 후에 각각에 테스트 케이스의 정답을 solve 함수를 통해 출력하는 방식으로 짰습니다. 혹시 제가 잘못 이해한 부분이 있거나 잘못 코딩한 부분이 있으면 답변부탁드리겠습니다.

    문제링크
    https://algospot.com/judge/problem/read/SORTGAME

    import java.util.Collections;
    import java.util.HashMap;
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Scanner;
    import java.util.Vector;
    
    public class Main {
    
        static HashMap <Vector<Integer>, Integer> toSort = new HashMap<>();
    
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            Scanner sc = new Scanner(System.in);
            int T = sc.nextInt();
            sc.nextLine();
            int test_case;
            for(int i = 1; i <= 8; i++)
                precalc(i);
            for(test_case = 0; test_case < T; test_case++){
                int size = sc.nextInt();
                sc.nextLine();
                Vector<Integer> perm = new Vector<Integer>();
                for(int i = 0; i < size; i++)
                    perm.addElement(sc.nextInt());
                sc.nextLine();
                int result = solve(perm);
                System.out.println(result);
            }       
    
        }
    
        public static void precalc(int n){
            Vector<Integer> perm = new Vector<Integer>();
            for(int i = 0; i < n; i++)
                perm.add(i);
            Queue<Vector<Integer>> q = new LinkedList<Vector<Integer>>();
            q.offer(perm);
            toSort.put(perm, 0);
            while(!q.isEmpty()){
                Vector <Integer> here = q.peek();
                q.poll();
                int cost = toSort.get(here);
                for(int i = 0; i < n; i++)
                    for(int j = 2; j <= n; j++){
                        reverse(here,i,j);
                        Vector<Integer> there =  new Vector<Integer>();
                        there.addAll(here);
                        if(!toSort.containsKey(there)){
                            toSort.put(there, cost + 1);
                            q.offer(there);
                        }
                        reverse(here,i,j);
                    }
            }
        }
    
        public static int solve (Vector<Integer> perm){
            int  n = perm.size();
            Vector<Integer> fixed = new Vector<Integer>();
            fixed.setSize(n);
            for(int i = 0; i < n; i++){
                int smaller = 0;
                for(int j = 0; j < n; j++)
                    if(perm.get(j) < perm.get(i))
                        smaller++;
                fixed.set(i, smaller);
            }
            return toSort.get(fixed);
        }
    
        public static void reverse(Vector<Integer> here, int start, int end){
            Vector<Integer> temp = new Vector<Integer>();
            for(int i = end - 1; i >= start; i-- ){
                temp.addElement(here.get(i));
            }
            for(int i = 0; i < end - start; i++)
                here.set(i+start, temp.get(i));     
        }
    
    }
    

    3년 전
3개의 댓글이 있습니다.
  • hyunhwan
    hyunhwan

    구현한 해결방법의 방향은 바람직해보입니다. 확인해보니 pre-calculation 과정에서 대부분의 시간이 소요되고 이로 인해 시간초과가 발생하는 것 같습니다. 시도 해보진 않았지만, 해당 방법에 약간의 수정으로 속도의 향상을 기대하는 방법은 reverse 함수를 보다 효율적으로 작성하는 방법이 있습니다. 또한, 통과된 Java solution을 기반하여 봤을 경우 HashMap 대신에 integer로 상태공간을 encoding하는 방법이 있습니다.


    3년 전 link
  • 정용진
    정용진

    모든 테스트 케이스를 다 만들어두고 계산을 하는 방식인듯 보입니다. 그리고 전제를 테스트값이 무조건 8개 들어온다고 잡으신거 같은데요. 테스트값은 1~8개가 들어오도록 되어있습니다.
    그리고 테스트 케이스를 다 만든다는건 8^8정도 되는거 같은데요.
    테스트 케이스를 만드는시간이 2초는 무조건 넘습니다.


    3년 전 link
  • 이석준
    이석준

    https://github.com/robin00q/Algorithm_and_CS/blob/master/Algorithm/%EC%A2%85%EB%A7%8C%EB%B6%81/29%EC%9E%A5_%EA%B7%B8%EB%9E%98%ED%94%84%EC%9D%98_%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89/29_2_Sorting_Game.md

    자바는 종만북대로 하면 시간초과가 난다고 하여 Integer을 이용한 상태공간으로 풀이하였습니다.

    참고하세요 ㅎ-ㅎ 3년전 글이지만 오늘의 저도 검색해서 들어왔기에 작성합니다.

    안에 코드도 있습니당. 문제되면 삭제할게요


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