[SWEA] 최대상금 JAVA

문제링크

SW Expert Academy

 

1. 문제의 이해 및 유형

Greedy...? 구현?

주어진 숫자판들 중 두개를 선택하여 정해진 횟수만큼 서로의 자리를 교환하여 최대 상금을 받는 문제이다.

어떠한 주어진 횟수를 돌렸을 때 가장 최대의 상금이 나오도록 해야하므로 항상 큰 것을 선택하도록 한다.

문제를 분석하고 풀면서 이게 과연 그리디인가 하는 의문이 들어 Greedy와 구현을 모두 써보았다.

의문점은 밑에서 확인하도록 해보자.

 

2. 문제 접근 방법

최대 자릿수는 6자리이고, 최대 교환 횟수는 10번이다.
주어진 숫자로 만들 수 있는 값의 상태공간은 중복이 없다는 가정 하에 720가지이다.
1가지 의경우의 수에서 1번 교환할 때 나올 수 있는 가지수는 15가지이다.

그렇다면 10번의 교환횟수를 모두 체크하게 되면 $15^10$이기 때문에 완전 탐색으로는 시간 안에 해결하기 힘들다.

또한, 중간중간 교환하면서 중복되는 값들도 존재하기 때문에 매우 비효율적이다.

 

모든 경우의 수가 아니라 어떤 특정한 경우에만 확인하면되겠다. 
선택한 값보다 오른쪽에 자신보다 큰 값들 중 가장 큰 값에 대하여 바꾸어 확인해보면 큰 값 중 하나일 것이다.

여기서 함정은 32888이라고 했을 때 
1회 교환의 최대 값은 82883이되지만 
2회 교환의 최대값은 88832가 되야한다. 

즉, 순간의 최댓값을 선택해야하는 것은 맞지만 i번째 순간의 최적이 i+1 번째 순간의 최적을 보장하지는 않는다는 점에서 Greedy한가 라는 의문이 든다.

그래서 선택 정렬(selection)을 하듯이 진행하면서 모든 경우에 대해 탐색해야 한다.

32888 이라면 82388 , 82838, 82883 3가지 경우를 모두 확인해보도록 한다.

 

종료조건을 생각해볼 때 다음 두 가지를 고려해야한다. 결국 우리가 만들 고자 하는 것은

'주어진 횟수'를 활용하여 '최댓값'을 만드는 것이기 때문이다.

1. 기본적으로 주어진 횟수를 모두 사용하는 경우

2. 횟수를 다 사용하기 전에 어떠한 최댓값을 만드는 경우.

어떤 주어진 값으로 만들 수 있는 가장 큰 값은 항상 정해져있다.
selection sort를 하듯이 진행한다했으므로 결국 어떤 n회에서 최댓값이 완성이 된다.

예시의 32888의 최대값은 88832 이므로 어느 순간 88832가 된다.
selection sort에서 잘 생각해보면 종료가 될 떄 마지막 비교했던 값의 위치(pos)는 배열의 마지막이라는 점을 생각해두자.

만약 주어진 횟수 M이 있을 때 n회 만에 만들어진 다면 M-n회가 남게된다. 우리는 이 남은 횟수 또한 무조건 교환을 해야한다. 

 

생각해보면, 짝수배로 남았다면 최댓값 -> ? -> 최댓값 과 같은 방식으로 진행하면 무조건 최댓값을 보장할 수 있다.

홀수라면? 홀수(2N+1)일 때도 2N번 이후 최댓값이 되고 그 최대값을 한번 교환해서 나오는 최댓값만 구하면 바로 구할 수 있게 된다.

54321 이라고 가정해보자. 이 값을 한 번만 교환하여 가장 큰 값을 만들어보면
54312와 같이 가장 낮은 자리의 숫자들끼리만 교환을 하면 된다.

하지만 만약 88832 라면? 

이부분에서 많이 놓치게 되어 88823이라고 대답할 수 있지만, 중복된 8과 8을 교환하게 되면

88832 그대로 최댓값을 유지할 수 있다. 이러한 부분을 고려하며 작성해보도록 하자.

 

정리하자면

1. findBest(int position, int cnt)함수를 구현하고자 한다.

2. Selection sort 진행방식과 마찬가지로 현재 위치보다 가장 큰 값을 찾아 교환해준다면,
  다음 위치를 찾고, 교환을 1회 진행하였으므로 findBest(position +1, cnt +1)을 진행해준다.

  이 과정을 우측의 모든 값들에 대해 진행하고 반복한다.

   2.1 만약, 교환할 값이 없다면 다음 값으로 넘어가되 횟수는 늘어나지 않는다.

 3. 종료조건의 확인

   1. 남은 횟수를 모두 채운 경우, 해당 횟수에서의 최대값을 기록하고 return

   2. 남은 횟수를 모두 채우기 전에 끝에 도달한 경우 (최대값을 미리 만든 경우)

    2.1 남은횟수가 짝수인지 홀수인지 구분하여 답을 return 한다.

import java.util.Scanner;

public class Solution {
    static char[] data;
    static int depth;
    static int max;
    static int ans;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        int T = sc.nextInt();
        for(int tt =1;tt<=T;tt++){
            ans =0;
            sb.append('#').append(tt).append(' ');
            data = sc.next().toCharArray();
            depth = sc.nextInt();
            findBest(0,0);
           // sb.append(Integer.parseInt(new String(data))).append('\n');
            sb.append(ans).append('\n');
        }
        System.out.println(sb);
    }
    public static void findBest(int pos, int cnt){
        //종료조건
        // 1. 남은 횟수가 없는 경우
        // 2. 남은 횟수가 있고, 끝에 도달한 경우(max를 찾음)

        //1. 남은 횟수가 없는 경우
        // 그대로 return

        if(cnt ==depth) {
            ans = Math.max(ans, Integer.parseInt(new String(data)));
            return;
        }

        //남은 횟수가 있고, 끝에 도달한 경우 즉, 지금이 가장 최대값.
        //이건 불변임. 무조건 가장 큰 값임.
        if(pos == data.length-1){
            ans = Integer.parseInt(new String(data));
            //(depth-cnt)%2 ==0 이면 다시 돌아올 수 있음.
            if((depth-cnt)%2 !=0){
                //한번만 바꾸었을 때 최대가 되는 값을 return해주어야함.
                //max값인상태임. 변화하지 않는 것이 가장 중요함.
                boolean flag = false;
                for(int i =0;i<data.length-1;i++){
                    if(data[i] == data[i+1]){
                        flag = true;
                        break;
                    }
                }
                //중복된 값이 없어 어떻게든 변화해야하는 경우.
                if(!flag){
                    swap(data.length - 1, data.length - 2);
                    ans = Integer.parseInt(new String(data));
                }
            }
            return;
        }
        
        //반복적으로 해야하는 일
        char max = data[pos];
        int maxIdx = pos;
        int maxValue = Integer.parseInt(new String(data));
        //자신보다 오른쪽에 있는 큰 수를 찾았음.
        //여러개 있을 수 있기 때문에 가장 큰 값을 찾아ㅜㄴ다.
        for(int i =pos+1;i<data.length;i++){
            if(data[i] >= max){
                max = data[i];
            }
        }
        //큰 수에 대해 확인하는 과정을 거친다.
        if(max == data[pos]) findBest(pos+1,cnt);
        else{
            for(int i = pos +1; i<data.length;i++){
                if(data[i] == max){
                    swap(i,pos);
                    findBest(pos+1, cnt+1);
                    swap(i,pos);
                }
            }
        }
    }
    static void swap(int a, int b){
        char tmp = data[a];
        data[a] = data[b];
        data[b] = tmp;
    }
}

3. 마치면서

재귀함수를 구현할 때는 항상 " 반복해야 하는 일" 과 "종료 조건"을 생각하여 작성하도록 한다.

 

종료조건이 두 가지인데 ans를 저렇게 구해도 답이 보장이 되나요? 하는 의문이 들 수 있다.

 

if(pos == length-1) 인경우 항상 최대값을 보장하고 답을 '정할 수 있다'

이후에 다른 상태에서 cnt == depth 인 부분에 도착한다고 했을 때,

어떠한 상태에서 이미 정해진 값보다 크다면 큰 값으로 정할 수 있기 때문에 보장할 수 있다.

if(pos == length-1)은 더이상 횟수를 늘리지 않고 더이상 해당 상태를 보지 않겠다는 뜻이다.