[BOJ 백준] 교환(1039) Java

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

1039번: 교환

 

문제 설명 : 

0으로 시작하지 않는 정수 N이 주어진다. 이때, M을 정수 N의 자릿수라고 했을 때, 다음과 같은 연산을 K번 수행한다.

1 ≤ i < j ≤ M인 i와 j를 고른다. 그 다음, i번 위치의 숫자와 j번 위치의 숫자를 바꾼다. 이때, 바꾼 수가 0으로 시작하면 안 된다.

위의 연산을 K번 했을 때, 나올 수 있는 수의 최댓값을 구하는 프로그램을 작성하시오.

 

입력 : 

첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다.

 

출력 : 

첫째 줄에 문제에 주어진 연산을 K번 했을 때, 만들 수 있는 가장 큰 수를 출력한다. 만약 연산을 K번 할 수 없으면 -1을 출력한다.

 

예제 입력 : 

16375 1

 

예제 출력 : 

76315

 

접근법 : 

1) 어떻게 풀 것인가?

이 문제에서 가장 중요한 조건은 K번을 반드시 실행한다는 것이다. 

 

예를 들어 190라는 숫자 N이 주어졌을때 K가 1일경우 910이 가장 큰 수가 되지만,

K가 2일 경우 901이 가장 큰 수가 된다.

 

따라서 이 문제는 최소 경우로 최고의 효율을 구하는 문제가 아니라,

기본적으로 K번 모두 수행해봐야 값을 알 수 있는 완전탐색 기반의 문제이다.

 

다만, K가 10이고 N은 최대 7자리수가 된다. 따라서 단순 BFS나 DFS를 실행한다면 실행시간초과 또는 DFS 함수 stack overflow가 발생할 수 있다. 최대 경우의 수 7*6/2(7개 중 2개를 뽑아서) ^ 10(10번 실행) 제곱 = 21^8만해도 378억이므로 초과한다. 

 

따라서 메모이제이션(Memoization) 을 통해 경우의 수를 가지치기하는게 매우 중요한 문제이다.

여기서 중요한 것은 메모를 하는 배열을 2차원으로 선언해야한다는 것이다.

 

특정 1번 실행했을 때 A라는 숫자가 나온것과 2번 실행했을때 A라는 숫자가 나온것은 전혀 다르다.

따라서 depth별 메모를 해줘야하고 2차원 배열이 필요하다.

 

참고 : 메모이제이션 위키피디아

https://ko.wikipedia.org/wiki/%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98

메모이제이션 - 위키백과, 우리 모두의 백과사전

 

관련 문제로 게임 (백준 1103, 문제 - https://www.acmicpc.net/problem/1103, 풀이 - https://subbak2.tistory.com/7) 를 풀어보는 것 추천. 

 

BFS나 DFS 모두 DP(메모이제이션)적 요소를 추가해서 푼다면 무리없이 풀릴 것으로 예상.

 

 

2) 시간복잡도

기본 완전탐색시에는 최악의 경우 7자리 숫자에서 10번의 교환을 실행해야하므로,

7*6/2(7개 중 2개를 뽑아서) ^ 10(10번 실행) 제곱 = 21^8만해도 378억 이상 -> 시간초과가 발생한다.

 

메모이제이션을 통해 DP 형태에 BFS, DFS를 접목할 경우.

문제에서 주어진 최대 자리수인 1,000,000 이라는 숫자가 들어왔다고 가정하면 엄청난 성능의 이득을 볼 수 있다.

왜냐면 아무리 교환을 해도 1,000,000 밖에 값이 나오지 않기 때문이다.

 

따라서 사실상 N을 6자리 숫자로 줄이는 효과가 있고 6자리 숫자를 완전탐색+메모이제이션을 통해 같은 depth, 숫자의 경우 실행하지 않는다고 하면 시간복잡도는 충분히 여유있다. (실제 실행시간 Java - 144ms)

 

 

3) 공간복잡도

10*1000000 int 배열 외에 작은 변수들로 충분하다. DFS를 할 경우에 함수 호출만큼 변수가 추가되지만

위의 배열 크기가 38Mbytes(10*1000000*4Bytes)정도로 여유 있으므로 충분하다.

 

 

4) 풀면서 놓쳤던점

- 문제 조건을 1,000,000 미만인 수로 잘못봐서 (실제는 1,000,000 까지 가능) 런타임 에러가 발생했다.

아마도 Index Out of Bound 예상.

 → 다시 한 번 문제 조건에서 범위 "이상", "초과" 에 신경쓰자.

 

- dfs 함수에서 return을 void로 하고 전역변수 정답을 갱신하는 형태로 시도해봤는데 함수 스택이 쌓여 stack overflow가 발생했다. 

 → 이중 Loop로 돌면서 dfs를 실행할때 void 형태로 하면 가지치기 구현이 매우 까다롭기 때문에, int 형태로 return 값을 받고 더 큰 값을 return 값에 갱신하는 형태로 수정했다.

 

 

5) 이 문제를 통해 얻어갈 것

삼성 SW역량테스트 A형(Advanced)에 충분히 출제될 수 있는 난이도.

경우에 따라 B형에서 활용될 수 있는 로직이 포함된 문제.

BFS, DFS로 기본 문제를 풀어봤다면 DP를 접목해서 입문하기 좋은 문제.

메모이제이션을 연습하기 아주 좋다.

 

 

Java 코드 : 

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

// 교환 백준 BOJ 1039
public class Main {

	static int K, len, sol;
	static String N;
	static int[][] visit;			// [변경횟수][최대숫자] 해당 변경횟수에서 숫자 방문시 메모이제이션으로 가지치기

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine());

		N = st.nextToken();				// String 형태의 N (자릿수 계산을 편하게 하기 위함) 
		K = Integer.parseInt(st.nextToken());

		len = N.length();
		visit = new int[K+1][1000001];		// [변경횟수] [최대숫자] 2차원 visit 배열
		
		sol = -1;		// 연산이 불가능하다고 가정하고 시작
		sol = dfs(N, 0);
		
		bw.write(String.valueOf(sol));

		br.close();
		bw.flush();
		bw.close();
	}

	static int dfs(String strN, int depth) {
		int num = Integer.parseInt(strN);
		if (depth==K) return num;	// depth가 K만큼 오면 끝
		
		int ret = visit[depth][num];
		if(ret!=0) return ret;		// 같은 depth에서 방문한 이력이 있으면 메모이제이션된 값 return
		
		ret = -1;					// 처음 방문한 경우 안된다고 가정하고(-1) 시작
	    for (int i = 0; i < len-1; i++)
	    {
	        for (int j = i+1; j < len; j++)
	        {
	        	if (i==0 && strN.charAt(j)=='0') continue;	// 0을 맨 앞으로 가져올 수 없음
	        	String tmpStr = swapLoc(strN,i,j);
	        	int tRet = dfs(tmpStr, depth+1);
	        	ret = tRet > ret? tRet:ret;
	        }
	    }
	    visit[depth][num] = ret;
	    return ret;
	}
	
	// String의 i, j 위치가 들어오면 바꿔주는 함수
	static String swapLoc(String str, int i, int j) {
		char[] chars = str.toCharArray(); 
		char tmp = chars[i];
		chars[i] = chars[j];
		chars[j] = tmp;
		return String.valueOf(chars);
	}
}