[SW Expert Academy] 1244번 - 최대 상금 문제(시간초과 미해결..)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15Khn6AN0CFAYD 

SW Expert Academy

정해진 횟수만큼 숫자들의 위치를 교환했을때 나올 수 있는 가장 큰 수를 구하면 되는 문제이다.

그리디 알고리즘 식으로 풀어야 하나..어떻게 해야 정해진 횟수만큼 교환시켰을때 최대한 큰 수가 나오게 할 수 있을까 고민되었다

어떻게 풀어야 할지 막막해서 댓글을 자세히 보지는 않았고 살짝 들여다보았다.

그리디 알고리즘으로 풀기는 어려운 모양이다..

딱 떠오르는 좋은 방법은 없지만 우선 최선을 다해 일단 풀어보았다.

 

아...중첩 for문을 이용해서 (3중for문 쓰고 난리도 아님..)어떻게든 모든 경우의 수를 알아보려 시도했으나

생각보다 어렵다

찾아보니 dfs 완전탐색법을 이용해 풀어야 하는 모양인데

dfs가 잘 생각이 안난다

이부분 공부하고 다시 시도해보기로 하고 일단 이 문제는 보류..

나중에 풀어보고 돌아와서 다시 글 작성하자

 

 

이 게시글을 쓰고 한달정도 지난 지금 다시 문제를 시도해보았다.

재귀로 완전탐색 하는 방법으로 시도해 보았으나 시간초과가 뜨길래

교환을 진행하다가 주어진 수들을 조합했을때의 가장 큰 수가 나왔을때, 남은 교환해야할 횟수가 짝수번 남았다면

그 값을 찾을 수 있다는 말이니까 return해서 그만 탐색하도록 하는 코드도 덧붙여 보았지만

그래도 시간초과를 뜨는것을 막을순 없었다..

d3문제 맞아.....?

나중에 또 시도해보겠다..

 

시간초과 코드

package D3;

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class SW_1244 {
    static StringBuilder sb = new StringBuilder();    //stringBuilder는 어떤 상황에서 쓰면 좋을까?
    static int max; //교환횟수만큼 교환했을때 나올 수 있는 최대값
    static int change; //교환 횟수
    static String ideal;
    static String tmpStr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());    //입력받을 테스트 케이스의 수

        char[] charArr;
        char[] tempArr;
        String tempStr;
        int count = 0;

        for (int i = 1; i <= T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            tempStr = st.nextToken();
            charArr = tempStr.toCharArray();    //오 이렇게하면 한번에 char 배열 만들어짐
            tempArr = tempStr.toCharArray();
            change = Integer.parseInt(st.nextToken());  //교환횟수
            //조합했을때 가장 큰 수 구하기
            //여기서 charArr자체를 정렬하면 안되고 따로 옮겨서 정렬해야함
            Arrays.sort(tempArr);
            for (int s = tempArr.length-1; s >= 0; s--) {
                sb.append(tempArr[s]);
            }
            ideal = sb.toString();

            change(charArr, count);
            bw.write("#" + i + " " + max);
            bw.newLine();

        }
        bw.flush();
        bw.close();


    }
    static void change(char[] chr, int count) {
        char temp;

        for (int i = 0; i < chr.length-2; i++) {
            for (int j = i + 1; j < chr.length; j++) {
                //교환,카운트 증가
                temp = chr[i];
                chr[i] = chr[j];
                chr[j] = temp;
                count++;

                tmpStr = String.valueOf(chr);
                if (tmpStr.equals(ideal) && (change - count) % 2 == 0) {    //ideal값과 같은데 남은 count횟수가 짝수번 남은상황이면
                    max = Integer.parseInt(ideal);
                    return; //ideal값을 만들 수 있다는 소리니까 더 안보고 돌아감
                }

                if (count == change) {  //change만큼 교환횟수를 채웠다면
                    String ctos = String.valueOf(chr);   //char배열 string으로 바꾸기
                    if (max < Integer.parseInt(ctos)) {   //int로 바꿔서 max랑 비교
                        max = Integer.parseInt(ctos);
                    }
                } else {
                    change(chr, count);
                }
                //카운트횟수 다시 감소,되돌려놓기
                count--;
                temp = chr[i];
                chr[i] = chr[j];
                chr[j] = temp;
            }
        }

    }
}