[Unsolved][JAVA] SWEA 1244 최대 상금

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15Khn6AN0CFAYD 

SW Expert Academy

 

 

1. 서론

 

한 끝 차이가 모든 것을 바꾼다는 것을... 알게 해 준 문제. 뭐 조합, 재귀 등등의 짬뽕 문제다.

누구는 dfs로 풀고 누구는 완전탐색으로 풀고 뭐로 풀고 다양하게 풀더라고요... ㅎ

 

2. 문제 풀이

 

문제 자체는 간단하다. 숫자가 주어지고 그걸 교환하는 횟수가 주어진다. 각 자리의 숫자를 n번 교환을 했을 때 얻을 수 있는 가장 큰 숫자를 구하는 문제이다.

 

- 내가 생각했던 풀이법

 

최초의 숫자를 교환할 조합을 구한다. 그리고 그 숫자를 조합에 맞게 교환한다. 그리고 그 교환된 숫자를 가지고 또 조합을 구해서 이를 n번 반복한다. 그리고 n번째로 조합을 마쳤을 때 최댓값을 비교해서 저장한다.

 

처음에는 자바가 익숙하지 않아서 문자열 복사하고 그러는걸 찾아보느라 시간을 엄청 날렸다. 

그렇게 코드를 완성했는데 왜인지 코드가 몇 개는 맞고 몇 개는 틀리게 나왔다.

 

import java.io.*;
import java.util.*;
 
public class Solution {
	
	static char[] s, tmp, check;
	static int n, ans;
	static int[] num, c;
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        
        int t = Integer.parseInt(br.readLine());
        
        for (int k = 1; k <= t; k++) {
        	StringTokenizer st = new StringTokenizer(br.readLine());
        	s = st.nextToken().toCharArray();
        	n = Integer.parseInt(st.nextToken());
        	
        	num = new int[s.length]; //전체 인덱스 중에서
        	
        	for (int i = 0; i < s.length; i++)
        		num[i] = i;
        	
        	c = new int[2]; //교환 할 번호를 뽑음
        	
        	ans = 0;
        	check = s.clone();
        	comb(0, 0);
        	
        	sb.append("#" + k + " " + ans + "\n");	
        }
        bw.write(sb.toString());
        br.close(); bw.close();
    }
    
    public static void comb(int cnt, int start) {
    	if (cnt == 2) {
    		tmp = swap(s.clone());
    		for (int i = 1; i < n; i++)
    			comb2(tmp.clone(), 0, 0);
    		ans = Math.max(ans, Integer.parseInt(String.valueOf(tmp)));
    		return;
    	}
    	
    	for (int i = start; i < s.length; i++) {
    		c[cnt] = num[i];
    		comb(cnt + 1, i + 1);
    	}
    }
    
    public static void comb2(char[] a, int cnt, int start) {
    	if (cnt == 2) {
    		tmp = swap(a);
    		return;
    	}
    	
    	for (int i = start; i < s.length; i++) {
    		c[cnt] = num[i];
    		comb2(a, cnt + 1, i + 1);
    	}
    }
    
    public static char[] swap(char[] a) {
    	char ch = a[c[0]];
    	a[c[0]] = a[c[1]];
    	a[c[1]] = ch;
    	return a;
    }
}

 

아마 조합이 제대로 안 도는 것 같은데 어디서 왜 어떻게 잘못되는지 논리적으로 못 찾겠어서(이미 하루 종일 너무 많은 시간 경과)

인터넷에서 내가 생각한 방법과 가장 유사한 코드를 찾았다.

 

 

https://brightj529.tistory.com/38

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

 

- 이 분의 풀이법

 

내가 생각한 것과 아이디어 자체는 유사하다. (구현 능력이 다름 ㅎ)

나는 조합 속의 조합 속의 조합.. 이었다면 이 분은 그 조합들을 리스트에 저장했다. (이게 바로 구현 능력의 차이)

그리고 그 리스트에 적힌대로 숫자의 자릿수를 교환하면서 최댓값을 구했다.

 

근데 코드가 이해는 가는데 나중에 이 문제 말고 이거랑 유사한 문제 나와서 이렇게 해봐! 하면 할 자신이 없음 ㅜ

 

3. 코드 설명

 

import java.io.*;
import java.util.*;
 
public class Solution {
	
    static char[] s;
    static int n, size, ans;
    static int[] c = new int[2];
    static List<int[]> lst = new ArrayList<int[]>(); //바꾸는 순서 저장
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        
        int t = Integer.parseInt(br.readLine());
        
        for (int k = 1; k <= t; k++) {
        	StringTokenizer st = new StringTokenizer(br.readLine());
        	s = st.nextToken().toCharArray();
        	n = Integer.parseInt(st.nextToken());
        	size = s.length; ans = 0;
        	
        	while (n > size)// 배열의 길이만큼만 교환해도 최댓값 구할 수 있음(시간 절약)
        		n -= 2;
       
        	comb(0, 0);
        	calc(0);
        	
        	sb.append("#" + k + " " + ans + "\n");
        	lst.clear();
        }
        bw.write(sb.toString());
        br.close(); bw.close();
    }
    
    public static void comb(int cnt, int start) { // 교환 조합
    	if (cnt == 2) {
    		lst.add(c.clone());
    		return;
    	}
    	
    	for (int i = start; i < size; i++) {
    		c[cnt] = i;
    		comb(cnt + 1, i + 1);
    	}
    }
    
    public static void calc(int cnt) { // 값 바꿔서 최댓값 구함
    	if (cnt == n) { //n번 교환하면서 최댓값 구하기
            ans = Math.max(ans, Integer.parseInt(new String(s)));
            return;
        }
        for (int i = 0; i < lst.size(); i++) {
            swap(i);
            calc(cnt+1);
            swap(i);  
        }
    }
    
    public static void swap(int i) { //교환
    	char ch = s[lst.get(i)[0]];
        s[lst.get(i)[0]] = s[lst.get(i)[1]];
        s[lst.get(i)[1]] = ch;
    }
}

 

그 분의 코드를 내 나름대로... 풀어봤다.

교환 횟수가 문자열의 길이보다 길어지면 시간이 오래 걸린다고 한다. 근데 어차피 문자열의 길이만큼만 교환해도 모든 교환의 경우를 얻을 수 있다고 한다. 그래서 중간에 while문으로 반복 횟수 조절하는 코드 있음!

comb함수로 조합을 구해서 lst 배열에 저장하고 calc함수에서 교환하면서 최댓값 구한다.

내 코드에서 보면 calc가 comb + calc이고 comb2가 comb역할을 한듯 ㅜ

그리고 그 분 코드에서는 swap함수가 따로 없었는데 그냥 만들어서 코드 정리했다!!

 

 

새로 알게된 자바 문법!!

 

처음에 StringBuilder로 받았다가 배열 복사하고 만들고 그런 거 머리 아파서 그냥 char[] 로 받았다.

String에 toCharArray 붙으면 char[]로 변환 가능!

이외에도 배열 복사 하려면 Arrays.copyof 쓰거나 clone() 쓰면 됨

그리고 new String(char[]); 이렇게 하면 String으로 만들어짐

 

C++ 보다 배열 복사나 문자열에 대해 신경 써줄게 너무 많아서 너무 킹받음... 자바 진짜 누가 만들었냐... 개불편하네 ㅠ