SWEA[1244] - 최대 상금[D3]

링크

SWEA[1244]

문제설명

• 완전탐색

문제풀이

• 완전탐색, MAX찾기, Length이상 Swap할 경우 2만큼 빼준다.(제자리로 되돌릴 수 있음)

문제코드

import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;

public class Solution1244{
    public static int Ans;
    public static char[] num;
    public static int S;
    public static int L;
    public static LinkedList<int[]> lst = new LinkedList<int[]>();
    public static int[] comb = new int[2];
    public static void Search(int cnt, int start) {
        if(cnt==2) {
            lst.add(Arrays.copyOf(comb, 2));
            return;
        }
        for (int i = start; i < L; i++) {
            comb[cnt]=i;
            Search(cnt+1,i+1);
        }
    }

    public static void Swap(int cnt) {
        if(cnt==S) {
            Ans=Math.max(Ans, Integer.parseInt(new String(num)));
            return;
        }
        char temp;
        for (int i = 0; i < lst.size(); i++) {
//            SWAP(lst.get(i)[0],lst.get(i)[1])
            temp = num[lst.get(i)[0]];
            num[lst.get(i)[0]] = num[lst.get(i)[1]];
            num[lst.get(i)[1]] = temp;
            Swap(cnt+1);
//            원상복구
            temp = num[lst.get(i)[0]];
            num[lst.get(i)[0]] = num[lst.get(i)[1]];
            num[lst.get(i)[1]] = temp;
        }
    }

    public static void main(String args[]) throws Exception
    {
        System.setIn(new FileInputStream("res/swea/1244.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T;
        T=Integer.parseInt(br.readLine());
        StringTokenizer st;

        for(int test_case = 1; test_case <= T; test_case++)
        {
            st = new StringTokenizer(br.readLine()," ");
            num = st.nextToken().toCharArray();
            S = Integer.parseInt(st.nextToken());
            L = num.length;
            while(S>L) {
                S=S-2;
            }

            Search(0,0);
            Swap(0);

            System.out.println("#"+test_case+" "+Ans);
//            초기화
            Ans=0;
            lst.clear();
        }
    }
}

아쉬운점

• NC2 구현하는데 오래걸렸음
  • Search(cnt+1,i+1)임
  • for문에서 다음원소만 고를 수 있도록
• Swap재귀함수에서 탈출구문을 실수로 Length로 설정했었음
  • 무조건 최대값 나왔었음.
• Swap횟수가 Length보다 길 경우 (특히, Length:6, Swap:10일 때) 시간초과발생
  • O(N) = (6C2)^10 = 5.7*10^12
  • Length만큼 Swap하면 어떤 숫자의 조합도 만들 수 있기 때문에 불필요함
    • (Length, Length-1) swap하면 최대값 이 나오게 됨
  • O(N) = (6C2)^6 = 1.1*10^7
• Swap>=Length면 그냥 최대값 내보내면 시간줄일 수 있음
  • 귀찮음

잘한점

• Char[]를 String생성자에 넣으면 알아서 String 만들어주는거 공부함
  • String str = new String(chararr);
• Length만큼 Swap하면 어떤 조합도 만들 수 있다는 것을 알고 Length기준으로 Swap 2씩 줄임.
  
  • 시간초과 해결