[SWEA] 1244 : 최대 상금

https://swexpertacademy.com/main/talk/solvingClub/problemView.do?contestProbId=AV15Khn6AN0CFAYD&solveclubId=AV6kld8aisgDFASb&problemBoxTitle=%5BD2~D3+%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4%5D+%EA%B8%B0%EC%B4%88+%EB%8B%A4%EC%A7%80%EA%B8%B0+Part4&problemBoxCnt=14&probBoxId=AV-4MojKLNADFATz 

SW Expert Academy

정해진 횟수만큼 꼭 교환을 해야 하기 때문에 최댓값을 갱신해서 하는 건 아니었다.

그리고 어차피 2번씩 교환하다보면 같은 수가 또 나오고 거기서 교환하면 또 똑같이 교환하고를 반복하기 때문에 

DP 배열을 만들어서 해당 횟수를 돌렸을 때 가장 큰 수를 저장해서 답을 출력했다.

DP를 갱신해야 하는데 저장된 값보다 작으면 바로 종료해서 불필요한 계산을 피했다.

 

내 코드

메모리 : 58640 KB

시간 : 200 ms

코드길이 : 1632 B

 

[내 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {
	static int max, length, changeTime;
	static boolean isFirst;
	static int[] DP;

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;

		int T = Integer.parseInt(br.readLine());
		for(int t = 1; t <= T; t++) {
			st = new StringTokenizer(br.readLine());
			sb.append('#').append(t).append(' ');
			isFirst = true;
			DP = new int[11];

			String str = st.nextToken();
			changeTime = Integer.parseInt(st.nextToken());
			
			length = str.length();
			
			for(int i = 0; i < length - 1; i++) {
				for(int j = i + 1; j < length; j++) {
					exchange(str, i, j, 1);
				}
			}
			sb.append(DP[changeTime]).append('\n');
		}
		System.out.print(sb);
	}
	
	static void exchange(String str, int first, int second, int change) {
		int[] number = new int[length];
		
		for(int i = 0; i < length; i++) {
			number[i] = str.charAt(i) - '0';
		}
		int temp = number[first];
		number[first] = number[second];
		number[second] = temp;
		
		StringBuilder sb = new StringBuilder();
		for(int i : number) {
			sb.append(i);
		}
		
		int realNum = Integer.parseInt(sb.substring(0, length));
		if(realNum < DP[change])
			return;
		DP[change] = realNum;
		
		if(change == changeTime)
			return;

		
		for(int i = 0; i < length - 1; i++) {
			for(int j = i + 1; j < length; j++) {
				exchange(sb.substring(0, length), i, j, change + 1);
			}
		}
	}
}

(오답)시간초과

package D3;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Q1244 {
	static int max;
	static int exchange;

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;

		int T = Integer.parseInt(br.readLine());
		for(int t = 1; t <= T; t++) {
			st = new StringTokenizer(br.readLine());
			sb.append('#').append(t).append(' ');
			max  = Integer.MIN_VALUE;
			
			String num = st.nextToken();
			int[] arr = new int[num.length()];
			for(int i = 0; i < num.length(); i++) {
				arr[i] = num.charAt(i) - '0';
			}
			exchange = Integer.parseInt(st.nextToken());
			
			change(arr, 0);
			
			sb.append(max).append('\n');			
		}
		System.out.print(sb);
	}
	
	public static void change(int[] arr, int time) {
		//현재 숫자가 최댓값이면
		max = Math.max(max, arrToNum(arr));
		if(time == exchange)
			return;
		for(int i = 0; i < arr.length - 1; i++) {
			for(int j = i + 1; j < arr.length; j++) {
				int temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
				change(arr, time + 1);
				temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
		}
	}
	
	public static int arrToNum(int[] arr) {
		int result = 0;
		for(int i = 0; i < arr.length; i++) {
			result += arr[i]*Math.pow(10, arr.length - 1 - i);
		}
		return result;
	}
}

[정답 코드]

메모리 : 23244 KB

시간 : 128 ms

코드길이 : 1503 B

import java.util.*;
import java.io.*;
 
class Solution
{
    static int max = Integer.MIN_VALUE;
    static char [] c;
    static Set<String> hs;
    static int length;
    public static void main(String args[]) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int T = Integer.parseInt(br.readLine());
         
        for(int test_case = 1; test_case <= T; test_case++)
        {
            max = Integer.MIN_VALUE;
            hs = new HashSet<>();
            StringTokenizer st = new StringTokenizer(br.readLine());
            c = st.nextToken().toCharArray();
            int n = Integer.parseInt(st.nextToken());
            length = c.length;
 
            dfs(n);
 
 
            System.out.printf("#%d %d\n", test_case, max);
        }
    }
 
    public static void dfs(int n) {
        String cur = String.valueOf(c);
 
        if(n == 0)
        {
            max = Math.max(Integer.parseInt(cur), max);
            return;
        }
         
        if(hs.contains(cur)) return;
        hs.add(cur);
 
 
        for(int i = 0; i < length; i++)
        {
            for(int j = i + 1; j < length; j++)
            {
                char temp = c[i];
                c[i] = c[j];
                c[j] = temp;
                dfs(n - 1);
                c[j] = c[i];
                c[i] = temp;
            }
             
        }
 
    }
     
}