[BOJ 백준] 교환(1039) C++

링크 : 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, 숫자의 경우 실행하지 않는다고 하면 시간복잡도는 충분히 여유있다. (실제 실행시간 C++ - 8ms, 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를 접목해서 입문하기 좋은 문제.

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

 

 

C++ 코드 : 

// 교환 1039 C++
#if 1
#pragma warning(disable:4996)
#include <cstdio>
#include <string>

using namespace std;

int N, K;
int ans;						// ans : 정답
int len;						// 몇자리 수인지 확인

char inputStr[7];
int visit[10 + 1][1000000 + 1];

void input();
int dfs(string str, int depth);
string swapLoc(string str, int i, int j);

int main() {
	// 1. 입력
	//freopen("input.txt", "r", stdin);
	input();

	// 2. dfs로 답 구하기
	// 연산이 불가능하다고 가정하고 시작
	ans = -1;
	ans = dfs(inputStr, 0);

	// 3. 답 출력
	printf("%d", ans);

	return 0;
}

void input() {
	// cin >> N>> K;
	scanf("%d %d", &N, &K);

	// 1) 숫자 몇자리수인지 확인
	len = 0;
	int checkN = N;
	while (checkN > 0) {
		len++;
		checkN /= 10;
	}

	// 2) 각 자리수 파싱해서 char 배열에 넣기
	checkN = N;
	for (int i = len - 1 ; i >= 0; i--) {
		inputStr[i] = checkN % 10 + '0';
		checkN /= 10;
	}
}

int dfs(string str, int depth) {
	int num = stoi(str);
	// depth가 K일때 최종적으로 값을 비교
	if (depth == K) {
		return num;
	}

	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++) {

			// 0은 맨 앞으로 가져올 수 없음
			if (i == 0 && str[j] == '0') continue;

			string tmpStr = swapLoc(str, i, j);
			int tRet = dfs(tmpStr, depth+1);
			ret = tRet > ret ? tRet : ret;
		}
	}
	visit[depth][num] = ret;
	return ret;
}

string swapLoc(string str, int i, int j) {
	char tmp = str[i];
	str[i] = str[j];
	str[j] = tmp;
	return str;
}
#endif