내가 푼 로직
(1) main 메서드 내부
-
List list 선언으로 입력받은 숫자를 한 자리씩 list.add(0, 숫자)로 입력
-
길이가 2인 1차원 int배열 plus(swap 할 num의 모음)와 1차원인 boolean배열 전역 선언/최대 교환횟수 count 전역 선언
-
find(list, 0) ➡️ list를 넘겨주고 for문으로 반복할 인덱스값(idx)을 0으로 넘겨준다.
find(List list, int idx) 내부 로직
(2) if문 내부
- 만약 idx = 2 ➡️ plus의 배열 2자리가 모두 찼다는 의미
이고 userCount < count ➡️ 현재 바꾼횟수(userCount) 가 최대교환 횟수인 count 보다 작다는 의미
▶️ 위 조건을 만족한다면 list.set을 활용해 list.get으로 값을 가져와 각 위치의 값을 swap한다.
- list의 뒤에서부터 앞으로 오면서 10배를 해주며 더하고 maxNum으로 최댓값 갱신
- userCount값(현재 교환횟수) 1증가
- 리턴
(3) for문
1. i = 0부터 list.size()만큼 돌며 visit[i]값이 false인 인덱스만을 찾는다 2. visit[i] = true로 하고 plus[idx]위치에 인덱스 값을 저장
3. find(list, idx+1) 로 재귀 들어감 4. visit[i] = false
코드
package com.edu.test;
import java.io.*;
import java.util.*;
public class SWEA_최대상금 {
public static boolean visit[];
public static int maxNum, count, idx, plus[], userCount;
public static void main(String args[]) throws Exception
{
for(int test_case = 1; test_case <= T; test_case++)
{
st = new StringTokenizer(br.readLine(), " ");
List<Integer> list = new ArrayList<>();
plus = new int[2];
int n = Integer.parseInt(st.nextToken());
int gop = 1;
int namu = 1;
while(n != 0) {
gop = n/10;
namu = n%10;
n = gop;
list.add(0, namu);
}
visit = new boolean[list.size()];
count = Integer.parseInt(st.nextToken());
find(list, 0);
sb.append("#"+test_case).append(" ").append(maxNum).append("\n");
maxNum = 0;
}
System.out.println(sb);
}
public static void find(List<Integer> list, int idx){
if(idx == 2 && userCount < count){
int sum = 0;
int a = plus[0];
int b = plus[1];
int aNum = list.get(a);
int bNum = list.get(b);
list.set(a, bNum);
list.set(b, aNum);
int gop = 1;
for(int i=list.size()-1;i>=0;i--){
sum += list.get(i)*gop;
gop *= 10;
}
maxNum = Math.max(a, maxNum);
userCount++;
return;
}
for(int i=0;i<list.size();i++){
if(!visit[i]){
visit[i] = true;
plus[idx] = i;
find(list, idx+1);
visit[i] = false;
}
}
}
}
위 로직에서 내가 실수한 부분
- 1 초과인 최대교환횟수인 경우 plus 배열을 계속해서 초기화해야하고 userCount 가 똑같은 경우도 분기처리해주어야 했다.
- 10배를 해주며 swap하는 로직이 매끄럽지 않다.
변경된 로직
-
String[] s라는 1차원 배열로 숫자를 입력받고, for문을 2차원으로 구현하여 두번째 for문은 첫번째 for문의 값보다 1만큼 큰 수로 시작하도록 구현한다.
이는 어찌되었건 간에, 두 수를 SWAP해야 하므로 for문을 이중으로 두어, 두 수를 고르면 된다. 그 전에, 첫번째 for문의 인자보다 두번째 for문의 인자값이 크거나 같으면 교환할 수 있도록 해야 한다.
-
탈출 로직 :: count값(내가 교환한 횟수)이 제시된 chance(최대 교환 횟수)와 같아지면 if문으로 탈출하도록 하며, String의 +=를 활용하면 쉽게 문자열인 숫자를 하나로 붙일 수 있고 그걸 바로 Integer.valueOf를 활용하면 된다.
import java.util.*;
import java.io.*;
class Solution
{
public static int chance, answer; //기회, 구하고자 하는 값
public static String s[]; //처음 받은 값들의 모임
public static void main(String args[]) throws Exception
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
for(int test_case = 1; test_case <= T; test_case++)
{
st = new StringTokenizer(br.readLine(), " ");
s = st.nextToken().split("");
chance = Integer.parseInt(st.nextToken());
answer = 0;
find(0, 0);//index시작 위치, 몇개의 비용을 소비했는지
sb.append("#"+test_case+" ").append(answer).append("\n");
}
System.out.print(sb);
}
public static void find(int idx, int count){
String finalNum = "";
String temp = "";
if(count == chance){
for(String n : s) finalNum+=n;
answer = Math.max(answer, Integer.valueOf(finalNum));
return;
}
for(int i=idx;i<s.length;i++){
for(int j=i+1;j<s.length;j++){
if(Integer.valueOf(s[i])<=Integer.valueOf(s[j])){
temp = s[i]; s[i] = s[j]; s[j] = temp;
find(i, count+1);
temp = s[i]; s[i] = s[j]; s[j] = temp;
}
}
}
}
} 