[SWEA 1244번] 최대 상금 with Java

guswls·2024년 5월 14일

알고리즘

목록 보기

33/39

문제

코드

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

class Solution {
	static int[] arr; // 숫자를 문자로 나타낸 배열
	static int maxCount; // 교환 횟수
	static int max; // 최대 값

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringBuilder sb = new StringBuilder();
		int N = Integer.parseInt(br.readLine());
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			String num = st.nextToken();
			covertArr(num);
			maxCount = Integer.parseInt(st.nextToken());
			max = 0;
			
            //이 부분이 핵심. 만약 숫자의 개수보다 교환 횟수가 더 크다면,
            //교환 횟수는 숫자의 개수만큼만 되어도 모든 교환을 할 수 있다.
            //예를 들어 숫자가 4개, 교환 횟수가 5번이라면, 5번째 교환부터는 이전과 중복된 교환이 일어난다.
			if(maxCount>arr.length) {
				maxCount = arr.length;
			}
			
			dfs(0, 0);
			
			sb.append(String.format("#%d %d\n", i + 1, max));
		}

		System.out.println(sb);
	}

	private static void covertArr(String num) {
		int size = num.length();
		arr = new int[size];
		for (int i = 0; i < size; i++) {
			arr[i] = num.charAt(i) - '0';
		}
	}

	static void dfs(int start, int count) {
		int size = arr.length;

		if (count == maxCount) {
			int ret = makeInteger(size);
			max = Math.max(max, ret);
			return;
		}

		for (int i = start; i < size - 1; i++) {
			for (int j = i + 1; j < size; j++) {
				swap(i, j);			
				dfs(i, count+1);					
				swap(i, j);
			}
		}
	}

	private static int makeInteger(int size) {
		int ret = 0;
		int pow10 = (int) Math.pow(10, size - 1);
		for (int i = 0; i < size; i++) {
			ret += arr[i] * pow10;
			pow10 /= 10;
		}
		return ret;
	}

	static void swap(int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
}

문제 이해

입력으로 교환할 숫자 와 교환 횟수가 주어진다.
예를 들어 123 1 이면 123의 각 자리를 한번만 교환해서 구할 수 있는 최대 숫자인 321이 답이 된다.
이때 교환은 횟수만큼 반드시 이루어져야 하고, 제자리 교환도 가능하다.
예를 들어 94 2라는 입력이 주어진다면 94 -> 49 -> 94, 와 같은 경우도 가능하다.

풀이 방법

이 문제의 경우 백트래킹을 통해 N개의 숫자 중 두 개씩 선택해 count만큼 변경하는 모든 조합에 대해서 생각하여야 한다.
dfs(int start, int count)로 선언한 다음, 바뀔 때 마다 count를 1씩 증가시켜준다.
만약 count == maxCount가 된다면, 상황에 따라 max값을 갱신한다.
이렇게만 구현한다면 시간초과가 발생하기 때문에 가지치기를 해야 한다.

이것이 main메서드의 아래 조건이다.

    if(maxCount>arr.length) {
                maxCount = arr.length;
    }

이 조건이 반드시 있어야 한다.

핵심 포인트

백트래킹을 하되, 시간초과가 발생하기 때문에 반드시 가지치기를 해주어야 한다. 이 가지치기가 핵심 포인트이다.

보완할 점 / 느낀 점

처음 문제를 봤을 땐, Greedy하게 접근하려 했다.
뭔가 만들수 있는 가장 큰 숫자부터 가장 작은 숫자까지 for문을 돌며 만약 교환 횟수(자리수가 다른 수)가 maxCount와 같다면 해당 숫자를 출력하도록 작성하려고 하였다.
하지만 같은 숫자가 존재하는 경우, 그리고 연속해서 같은 자리를 바꾸는 경우를 고려하는 것이 너무 어려울 것 같아 해답을 찾아보았다.
최근 dfs나 백트래킹문제를 안푼지 오래되어 감을 약간 잃은 것 같다. 한동안 계속 연습해야겠다.