[Java] SWEA 1244 최대 상금

Lee GaEun·2024년 11월 1일

JAVA 알고리즘 SWEA

[Java] 알고리즘

목록 보기

10/93

1244 최대 상금 문제 링크

문제분석

주어진 숫자판을 정해진 횟수만큼 교환하여 만들 수 있는 숫자의 가장 큰 값 출력

제약 사항

숫자판 : len(숫자판) <= 6
교환횟수 : 교환횟수 <= 10

입력 조건

첫째 줄 : 테스트 케이스 수 ( T <= 10 )
둘째 줄 : 숫자판 + 교환횟수

출력 조건

#부호 + 테스트 케이스 번호 + 공백 + 최대 숫자판 출력

#1

change 해서 최댓값을 반환 -> 반복

import java.util.ArrayList;
import java.util.Scanner;
import java.io.FileInputStream;

class Solution
{
    public static void main(String args[]) throws Exception
    {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        for(int test_case = 1; test_case <= N; test_case++)
        {
            int answer = 0;
            String number = sc.next();
            int change = sc.nextInt();

            for(int j=0; j<change; j++) {
                String com = "00";
                number = changeList(number, number.length(), com, 0);
            }

            System.out.println("#" + test_case + " " + number);
        }
    }
    static String changeList(String number, int len, String com, int i) {
        if (len-1==i) return com;
        char y = number.charAt(i);
        for(int j=i+1; j<len; j++) {
            char[] copyN = number.toCharArray();
            copyN[i] = copyN[j];
            copyN[j] = y;
            com = com.compareTo(String.valueOf(copyN)) < 0 ? String.valueOf(copyN) : com;
        }
        com = changeList(number, len, com, i+1);

        return com;
    }
}

이렇게 하면 최적해가 아님
중간에 최댓값이 아니여도 마지막에 최댓값인 걸 찾아야됨

4/30 다시 풀어봄

#2

50분


import java.util.HashMap;
import java.util.Scanner;
import java.io.FileInputStream;

/*
   사용하는 클래스명이 Solution 이어야 하므로, 가급적 Solution.java 를 사용할 것을 권장합니다.
   이러한 상황에서도 동일하게 java Solution 명령으로 프로그램을 수행해볼 수 있습니다.
 */
class Solution
{
    public static void main(String args[]) throws Exception
    {
        Scanner sc = new Scanner(System.in);
        int T;
        T=sc.nextInt();

        for(int test_case = 1; test_case <= T; test_case++)
        {
            String N = sc.next();
            char[] arrN = new char[N.length()];
            for(int i=0; i<N.length(); i++) {
                arrN[i] = N.charAt(i);
            }
            int C = sc.nextInt();
            C = Math.min(C, N.length());
            int result = dfs(arrN, 0, C, 0);

            System.out.println("#"+test_case+" "+result);
        }
    }

    static int dfs(char[] arrN, int level, int C, int max) {
        if(level==C) {
            String result = "";
            for(int i=0; i<arrN.length; i++) {
                result += arrN[i];
            }
            return Integer.parseInt(result);
        }

        char a;
        for(int i=0; i<arrN.length; i++) {
            for(int j=i+1; j<arrN.length; j++) {
                a = arrN[i];
                arrN[i] = arrN[j];
                arrN[j] = a;

                max = Math.max(dfs(arrN, level+1, C, max), max);
                // 각 단계마다 모든 swap의 경우를 구해서 max를 갱신

                a = arrN[i];
                arrN[i] = arrN[j];
                arrN[j] = a; // 빽트래킹으로 원본값 유지
            }
        }

        return max;
    }
}