• Home
  • About
    • JOOS photo

      JOOS

      Joos's blog

    • Learn More
    • Email
    • Github
  • Posts
    • All Posts
    • All Tags
  • Projects

1244. [S/W 문제해결 응용] 2일차 - 최대 상금

21 Nov 2018

Reading time ~1 minute

문제: https://www.swexpertacademy.com/main/code/problem/problemDetail.do

1. dfs

package com.company;


import java.util.*;

public class Main { //    dfs방식
    private static final Scanner sc = new Scanner(System.in);
    private static int result, maxCount;
    private static boolean[][] check;

    public static void main(String args[]) {
        int max = sc.nextInt();

        for (int i = 1; i < max+1 ; i++) {
            String number = sc.next();
            maxCount = sc.nextInt();

            check = new boolean[maxCount + 1][1000000]; // 같은 횟수이면서 같은 숫자를 탐색했는지 체크
            result = 0;

            changeNumber(number.toCharArray(), 0);
            System.out.println("#" + i + " " + result);

        }
    }
    public static void changeNumber(char[] numberChar, int nowCount){
        if (maxCount == nowCount){
            //횟수만큼 바꿨으면 결과 입려하고 종료
            result = result > getInteger(numberChar)? result : getInteger(numberChar);
            return;
        }
        int max = numberChar.length;
        for (int i = 0; i < max - 1; i++) {
            for (int j = 0; j < max ; j++) {
                char[] tempNumber = swap(numberChar, i, j); // 해당 자리 바꾼 char[] 받아오기
                if (!check[nowCount+1][getInteger(tempNumber)]) { // 같은 횟수이면서 같은 숫자를 탐색하지 않으면 탐색
                    check[nowCount+1][getInteger(tempNumber)] = true;
                    changeNumber(tempNumber, nowCount+1);
                }
            }
        }
    }

    public static int getInteger(char[] numberChar) {
        return Integer.valueOf(String.valueOf(numberChar));
    }

    public static char[] swap (char[] numberChar, int point1, int point2){ //해당 자리의 숫자 바꾸기
        char[] tempNumber = numberChar.clone();
        char num = tempNumber[point1];
        tempNumber[point1] = tempNumber[point2];
        tempNumber[point2] = num;
        return tempNumber;

    }
}



algorithmjavasamsung Share Tweet +1