[SWEA] 1244. 최대 상금

문제

1244. [S/W 문제해결 응용] 2일차 - 최대 상금
숫자판들이 주어지면 주어진 교환 횟수만큼 두 개씩 선택해서 위치를 교환한다. 숫자판들을 이어붙였을 때 숫자가 가장 큰 것을 출력하라.

• 무조건 교환 횟수만큼 교환 해야된다.
• 교환한거 또 교환해도 된다.

풀이

순열 문제 같은데 나는 선택정렬과 비슷하게 풀었다. 약간 그리디라고 생각하는데 잘 모르겠다 ;-; 아무튼 복잡하게 풀었다!!!!

1. 가장 오른쪽에 있는 큰 수를 찾는다. (인덱스 lidx , 값 max 저장)
2. 왼쪽부터 lidx 이전까지의 수 중에 가장 큰 수보다 작은 수를 찾는다. (인덱스 sidx , 값 min 저장)
   • 가장 작은 수로 하면 가장 큰 수가 맨 앞으로 가지 않기 때문이다.
3. sidx를 처음에 -1로 초기화했으므로, sidx>-1 이면 작은수가 큰 수보다 왼쪽에 있다.
   3-1. swap! (num[lidx], num[sidx])
   3-2. 교환 횟수를 +1 해준다. (주어진 교환 횟수와 일치하면 함수 종료)
   3-3. 교환 후, 큰 수가 위치하게 된 인덱스는 sidx가 된다. 이때 num[sidx]==num[sidx-1] 이면, 두 수가 일치한다는 것이고 경우의 수가 1개 더 생기게 된다. 따라서 교환횟수를 -1 해준다.
   

(3-3 예시) 
주어진 수 : 23888
3은 3번째, 4번째, 5번째 8과 교환이 가능하다.
2도 마찬가지!

이때, 내가 적용한 방식에 따르면 다음과 같은 순서로 작동한다.
-----
32888
82883
88823
-----
2와 3이 서로 교환한 8이 같은 숫자이기 때문에, 서로 다른 숫자와 교환했다고 하면 2와 3의 자리도 교환할 수 있다. 
따라서 [교환횟수-1] 을 해 주었다.

4. 위 1~3 을 반복한다. lidx+1 로 파라미터를 넘겨서 가장 큰 값 다음부터 교환한다.
5. 정렬이 완료됐을 때
   • case 1: 중복되는 수가 있으면 바로 끝낸다. (중복끼리 교환하면 결과가 똑같음)
   • case 2: 남은 횟수만큼 맨 뒤에 두 자리를 바꿔준다.

자바코드

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

class Solution
{	
	static int changeCnt=0;
	static int cnt=0;

	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		String numStr;
		for(int test_case = 1; test_case <= T; test_case++)
		{	
			changeCnt = 0;
			numStr = sc.next();
			cnt = sc.nextInt();
			int [] num = new int[6];
			for (int i=0; i<numStr.length(); i++) {
				num[i] = numStr.charAt(i) - '0';
			}
				
			change(num, 0, numStr.length());
			System.out.printf("#%d ", test_case);
			for (int i=0; i<numStr.length(); i++) System.out.print(num[i]);
			
			System.out.println();
		}
	}
	
	public static void change(int [] num, int start, int end) {
		int lidx = end-1, sidx=-1;
		int max = -1;
		
		for (int i=end-1; i>=start; i--) {
			if (num[i] > max) {
				lidx=i;
				max=num[i];
			}
		}
		
		int min = max;
		
		for (int i=start; i<lidx; i++ ) {
			if (num[i] < max) {
				sidx = i;
				min=num[i];
				break;
			}
		}
				
		if (sidx > -1) {
			// 작은 수가 가장 큰 수보다 앞에 있는 경우
			num[lidx] = min;
			num[sidx] = max;
			changeCnt++;
			if (sidx>0 && num[sidx]==num[sidx-1]) changeCnt--;
			
			if (changeCnt == cnt) return;
			
			change(num, sidx+1, end);
		} else if (lidx == end-1) {
			// 정렬이 이미 완료된 경우
			// case 1: 중복되는 수가 있는 경우 바로 끝
			for (int i=1; i<end; i++) {
				if (num[i] == num[i-1]) return;
			}
			
			// case 2: 남은 횟수만큼 맨 뒤에 두 자리 바꿔주기 
			while (changeCnt < cnt) {
				int temp = num[lidx];
				num[lidx] = num[lidx-1];
				num[lidx-1] = temp;
				changeCnt++;
			}
		} else {
			// 가장 큰 수가 작은 수보다 앞에 있는 경우 
			change(num, lidx+1, end);
		}
	}
}

틀린이유

중복을 고려 못해서!!!!

• 5번 처리 중복이 있을 때도 맨 뒤에 두 자리를 바꿨었음
• 3-3 처리..

---

어디가서 설명은 못 하겠는데 나는 만족하는 풀이 ㅋㅅㅋ