💡 Idea
문제에서 원하는 것
- 카드를 n번 교체
- 교체해서 결국엔 최대의 숫자를 원함
가장 큰 수를 만드는 방법은 가장 큰 숫자를 앞으로 보낸다라고 생각
하지만 여기서 문제는 32888에서 그 다음은 가장 큰 8과 가장 작은 2를 교체하는 38882가 아니라 82838이다..여기서 if문을 붙여가면서 어떻게 해볼라다가 이건 아니라는 생각이 들었다.
그 외에는 최대값보다 작은 수가 몇 개 존재하냐를 따지고..뭐 이런 생각을 해보다가
이거..그냥 다 교체해보고 그 중 가장 큰 수를 고르는 걸 지도? 라는 생각이 들었고 숫자가 최대 6자 뿐이길래 이 방법이 가능하다고 생각했다.
하지만 실제로 구현은 하지 못했고, 여러 블로그들을 다니면서 참고했다.
🤔 이해가 안되네?..
https://velog.io/@sua_ahn/SWEA-1244-%EC%B5%9C%EB%8C%80-%EC%83%81%EA%B8%88-Java
참고한 블로그에 내용이다. 깔끔하게 코드를 구현하셔서 보기가 좋았다.
완전탐색을 위해서 dfs를 사용하셨는데 나 스스로 이해가 잘 안되서 공책에 직접 써보면서 납득을 했다.
1. dfs인데 visited[] 안 써도 돼?
라는 생각이 가장 먼저 들었다.
for(int i = start; i < arr.length; i++) {
for(int j = i + 1; j < arr.length; j++) {
swap
dfs(i, cnt + 1);
swap한 거 복구
}
}왜냐하면 이렇게 돌게 되면
- for(0~4) 안에 for(1~4)에서 0,1인덱스를 교체하고
- 다시 dfs(0,1)을 하면 또 for(0~4)안에 for(1~4). 똑같은 반복문 또 하고 있는거다..
여기서 살짝 멘붕이 왔다. 똑같은 행동을 뭐하러 다시 하지..? 이러면서 이해가 막 꼬였는데..
이 문제에서는 그래도 된다!! 무슨 말이냐면
49에서 최대 숫자를 만들기 위해 2번의 교체가 주어지면
49 -> 94 -> 49로 만들 것이다. 이 예를 생각하니 바로 이해가 되었다!
2. 교체횟수 > 숫자의 총 길이에 경우
// 시간초과 최적화
if(arr.length < chance) { // swap 횟수가 자릿수보다 클 때
chance = arr.length; // 자릿수만큼만 옮겨도 전부 옮길 수 있음
}이 코드도 보고 솔직히 이해가 안갔다..
왜냐하면 문제에서는 분명히 이미 최대라도 정해진 횟수를 모두 채워야한다고 되어있다.
예를 들어 1234이고 내가 4번 교체해서 4321을 만들었다고 치자 그럼 1번이 남아서 어쩔 수 없이 4312를 만든다던가? 그런 경우가 생길 수 있기 때문에 무조건 남은 횟수를 채워야한다..이렇게 강박에 사로잡혔다!
하지만 이 부분도 다시 생각해보면 만약에 4321->4312로 되는 경우도 분명 있을거지만, 반복문을 모두 돌았을 때 이게 최대로 남지는 않는다. 길이만큼의 교체 횟수가 주어진다면 반복문을 돌면서 4321로 만들어지는 경우가 반드시 있다.
예를 들어 1234에서 의미없이 1회를 뻘짓을 한 번 한다고 생각하자.
1324 라고 쳤을 때 이 때 4번 교체를 해서 4321을 못 만들까? 아니다!!
그러니까
자리 수만큼의 교체 횟수가 주어지면 무조건 최대로 구성이 가능(남는 횟수는 그냥 의미없는 교환을 한다고 생각하자!!)
📋 회고
DFS 문제를 여럿 풀었는데 아직 내가 감을 제대로 못 잡은 거 같다.
솔직히 처음에도 DFS문제를 위해서 공책에 적고 몇 시간씩 이해해보려고 했는데 잘 안되었다. 내 사고가 자연스럽게 이해가 안된다고 해야하나..
DFS를 통해서 순열,조합 등의 문제를 직접 구성해보면서 사고를 좀 유연하게 바꿀 필요가 있다...
💻 성공 코드
static int max = 0;
static int changeNum;
static String[] ary;
public static void main(String args[]) throws Exception
{
Scanner sc = new Scanner(System.in);
int T=sc.nextInt();
for(int test_case = 1; test_case <= T; test_case++)
{
System.out.print("#" + test_case + " ");
ary = sc.next().split("");
changeNum = sc.nextInt();
max =0;
//10번을 넘어가는 횟수 => 숫자 길이만큼 조정
if(changeNum > ary.length)
changeNum = ary.length;
//DFS로 교환 과정마다 직접 MAX와 확인!
DFS(0,0);
System.out.println(max);
}
}
private static void DFS(int s, int changeCheck) {
//종료조건 : 교환이 다 이루어졌다!
if(changeCheck == changeNum){
String num = "";
//현재까지 모은 ary를 int형으로~
for (String piece : ary)
num += piece;
max = Math.max(max, Integer.parseInt(num));
return;
}
//직접 숫자들을 교환하는 과정!
for(int i = s ; i < ary.length; i++){
for(int j = i+1 ; j < ary.length; j++){
//교체
String temp = ary[i];
ary[i] = ary[j];
ary[j] = temp;
//DFS
DFS(i, changeCheck+1);
//교체복구
temp = ary[i];
ary[i] = ary[j];
ary[j] = temp;
}
}
}