[JAVA] 1039 교환

안녕하세요.

 

마지막 게시물이 5월..인데 지금은 어느덧 11월이 다가오고 있습니다.

 

무슨 일이 있었나 설명을 드리고 싶은데, 아무 일도 없었습니다.

 

안 한 이유를 설명하는 건 너무 긴 글이 될 것 같아서 바로 문제 풀러 가겠습니다. 

 

오늘의 문제는

https://www.acmicpc.net/problem/1039

1039번: 교환

교환은 영어로 change이죠. 아 아니죠 change는 변화인데 trade가 맞는 것 같습니다. 

 

<나의 풀이>

 

문제의 조건을 먼저 보자면 자연수 n <= 1,000,000 , k <=10,  < 2초로 주어졌습니다. 

 

n은 교환될 숫자, k는 얼마나 교환이 이루어지는 지에 대한 횟수를 의미합니다.

 

그리고 k번 교환 후, 최대 값을 가지는 n을 출력해야합니다.

 

1. 답을 구하는데 특정한 기준을 통해 해결시도

 

처음 문제를 보고 '최대 값 = 모든 케이스를 다 확인'이 생각이 나서 모든 케이스를 다 확인하는 방법으로 생각했습니다.

 

하지만 시간복잡도를 계산하다 보니, O(n^k)로 모든 경우를 구하는 것은 힘들다고 판단하여 다른 방법을 찾아봤습니다. 

 

가장 큰 n을 구하는 것을 어떠한 교환에서도 숫자가 항상 가장 커지게 만들면 문제를 해결할 수 있다고 생각했습니다. 

 

항상 가장 커지게 교환을 하는 방법에 대해 간략하게 설명을 하자면

 

ㄱ. 주어진 n을 정렬한다

n = "4921" ,sortn = "1249" 

 

ㄴ. n의 첫 번째 자리와 sortn의 첫자리를 비교한다

투포인터를 사용하여 각 포인터를 이동시키며 비교

n.charAt(pointer1) is same sortn.CharAt(pointer2) ?

 

ㄷ. 다르다면 n의 첫 번째 자리와 n에서 sortn의 첫자리를 찾아서 교환한다.

chage pointer1 to pointer3(find sortn.CharAt(pointer2) in n)

 

하지만 이 알고리즘은 다양한 예외 상황에 적용하지 못했습니다. 사실 적용시키려고 여러 조건을 추가해 보았습니다.

 

a) n의 길이가 1이면 -1을 리턴

b) n의 길이가 2이고 그 1의 자리가 0이면 -1을 리턴

 

ㄱ. 주어진 n을 정렬한다

n = "4921" ,sortn = "1249" 

 

ㄴ. n의 첫 번째 자리와 sortn의 첫자리를 비교한다

투포인터를 사용하여 각 포인터를 이동시키며 비교

n.charAt(pointer1) is same sortn.CharAt(pointer2) ?

 

c) 포인터들이 순회를 마치면 n의 가장 2자리만 교환

 

ㄷ. 다르다면 n의 첫 번째 자리와 n에서 sortn의 첫자리를 찾아서 교환한다.

chage pointer1 to pointer3(find sortn.CharAt(pointer2) in n)

 

코드

import java.io.*;
import java.util.*;
public class Num1039 {
	 static String n;
	 static String decendingn ;
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		String[] input = bf.readLine().split(" ");
		n = input[0];
		decendingn = sort(n);
		int k = Integer.parseInt(input[1]);
		int len = n.length()-1; 
		int maxvalue = -1;
		int nowpointer =0;
		
		if(n.length()==1 && k>0){
			System.out.println(-1);
			return;
		}
		if(n.length()==2 && n.charAt(1)=='0') {
			System.out.println(-1);
			return; 
		}
		for(int i=0;i<k;i++) {
			while(true) {
				if(len<0 || nowpointer>=n.length()){
					if(hasSameNumber()) {
						break;
					}
					char[] arr = n.toCharArray();
					char lchar = arr[n.length()-1];
					arr[n.length()-1] = arr[n.length()-2];
					arr[n.length()-2] = lchar;
					n = String.valueOf(arr);
					break;
				}
				if(n.charAt(nowpointer)==decendingn.charAt(len)) {
					nowpointer++;
					len--;
				}else {
					change(nowpointer,len);
					nowpointer++;
					len--;
					break;
				}
			}
			
		}
		System.out.println(Integer.parseInt(n));
	}
	
	public static String sort(String n) {
		char[] arr = n.toCharArray();
		Arrays.sort(arr);
		return String.valueOf(arr);
	}
	public static String change(int nowindex, int maxindex) {
		int maxvalue = Character.getNumericValue(decendingn.charAt(maxindex));
		for(int i=n.length()-1; i>=0;i--) {
			if(Character.getNumericValue(n.charAt(i))==maxvalue) {
				char[] arr = n.toCharArray();
				char lchar = arr[nowindex];
				arr[nowindex] = arr[i];
				arr[i] = lchar;
				n = String.valueOf(arr);
				return n;
			}
		}
		return "-1";
	}
	public static boolean hasSameNumber() {
		for(int i=0;i<n.length();i++) {
			if(n.charAt(i)!=n.indexOf(n.charAt(i))){
				return true;
			}
		}
		return false;
	}
}

 

이 알고리즘의 핵심 기준은 '항상 가장 큰 값으로 교환하는 것이 최대 값을 구하는 것이다'라는 그리디 알고리즘과 비슷한 형태를 가지고 있습니다.

 

하지만 381993과  같은 경우 위의 기준을 따르지 않는 것을 확인할 수 있습니다..!

 

381993 > 981933 > 991833 > 998133  

 

381993 > 981393 > 989313 > 998313 

 

---

2. BFS를 이용한 풀이

문제의 유형 태그를 보고 BFS로 접근해 봐야겠다고 생각해 보았습니다.

 

이 문제를 왜 BFS로 해결해야 하는가에 대해 생각을 해보고 가겠습니다. 

 

우선 제가 이해하는 BFS는 하나의 그림을 표현할 수 있는데

위 그림처럼 현재 단계에 모든 경로를 확인하고 그다음 단계로 넘어가는 탐색 방법이라고 생각합니다. 이러한 탐색 방식이 주는 특징은 바로 같은 거리에 있는 노드들끼리 비교가 가능하다는 점입니다. 

 

다시 문제로 돌아와 거리를 교환의 횟수라고 생각해 보겠습니다. 모든 경우를 확인해야 한다는 것은 첫 번째 풀이를 통해 얻은 단 하나의 교훈입니다. 모든 경우라는 말을 좀 더 풀어서 보자면, (k번 교환했을 때 나온 n의) 모든 경우라는 것을 알 수 있습니다. 결국 다시 한번 말하자면 거리가 k인 노드들에 대한 비교가 필요한 것입니다.

 

BFS로 해결해야 하는 거 오케이 하지만 더 큰 문제가 남아있습니다. 

 

교환은 사실 이항계수와 같은 경우의 수를 가집니다. 이러한 교환을 10번 반복하면...그 수를 계산하는 것조차 힘든 수가 나옵니다. 그렇다면 어떻게 최적화를 시켜줄 수 있을까에 대한 고민이 필요합니다. 저는 저 나름대로의 최적화로 코드를 구현했습니다. (코드 표시)

 

<코드>

import java.io.*;
import java.util.*;

class Node{
	String value;
	int k;
	public Node(String value, int k) {
		this.value = value;
		this.k=k;
	}
}

public class Num1039_2 {
	static Queue<Node> que = new LinkedList<>();
	static int[] maxValue = new int[12];
	
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		String[] inputs = bf.readLine().split(" ");
		String n = inputs[0];
		int k = Integer.parseInt(inputs[1]);
		Arrays.fill(maxValue, -1);
		maxValue[0] = stringToNum(n);
		que.add(new Node(n,0));
		while(!que.isEmpty()) {
			Node now = que.poll();
			if(now.k<10) {
				change(now);
			}
		}
		System.out.println(maxValue[k]);

	}
	public static void excute(Node now) {
		if(maxValue[now.k]<stringToNum(now.value)) {
			maxValue[now.k] = stringToNum(now.value);
		}
		
	}
	public static void change(Node now) {
		char[] charArr = now.value.toCharArray();
		for(int i=0;i<now.value.length()-1;i++) {
			for(int j=i+1;j<now.value.length();j++) {
				char tmpchar = charArr[i];
				charArr[i] = charArr[j];
				charArr[j] = tmpchar;
                //교환에서 나온 값들 중 작아지는 값들은 que에 넣지 않는다.
				if(stringToNum(String.valueOf(charArr))> maxValue[now.k+1]) {
					if(String.valueOf(charArr).charAt(0)!='0') {
						Node nxt = new Node(String.valueOf(charArr),now.k+1);
						excute(nxt);
						que.add(nxt);
					}
				}
				charArr[j] = charArr[i];
				charArr[i] = tmpchar;
			}
		}
	}
	public static int stringToNum(String st) {
		return Integer.parseInt(st);
	}
}

문제 해결..!

했지만 지금 와서 다시 최적화 조건에 대해서 생각해 보니 이상하다는 생각이 들었습니다. 

maxValue라는 arr에 index는 k를 의미하는데, 제가 설정한 조건을 풀어서 써보자면

 

숫자를 교환하였을 때, 그 교환한 숫자가 교환해 왔던 숫자보다 작다면 패스.

 

아무리 생각해 봐도 이 조건은 뭔가 이상한데.. 왜 문제가 풀렸는지는 의문입니다. 가장 의문인 점이 만일 교환 초기에 가장 큰 수가 나왔을 때, 다른 경우들을 패스하여 큐에 넣어주지 못해서 나중에 값을 구하지 못하는 것입니다.

 

이 부분을 증명해 보기 위해 교환을 위한 순회를 역순으로 설정해 보았습니다. 그래도 정확한 값이 나옵니다..ㅠ

이 조건이 정말 타당해서 그런지 제가 반례를 생각을 못하는 것인지 아직은 알 수가 없어서 답답하네요.

 

다른 분들의 풀이를 보니 보통 vist[1,000,001][k] arr을 만들어서 이미 방문한 노드들은 다시 넣어주지 않는 것으로 최적화를 하신 것 같습니다. 

 

후기

1. 문제를 보고 어떤 유형으로 풀어야 하는지에 대한 생각 연습하기

2. 조건이 점점 많아지고 코드가 이상해지고 싸해지면.. 흠 생각을 다시 한번 해보기

3. 반례.. 찾아줘