1244. [S/W 문제해결 응용] 2일차 - 최대 상금
숫자판들이 주어지면 주어진 교환 횟수만큼 두 개씩 선택해서 위치를 교환한다. 숫자판들을 이어붙였을 때 숫자가 가장 큰 것을 출력하라.
순열 문제 같은데 나는 선택정렬과 비슷하게 풀었다. 약간 그리디라고 생각하는데 잘 모르겠다 ;-; 아무튼 복잡하게 풀었다!!!!
lidx
, 값 max
저장)sidx
, 값 min
저장) (3-3 예시)
주어진 수 : 23888
3은 3번째, 4번째, 5번째 8과 교환이 가능하다.
2도 마찬가지!
이때, 내가 적용한 방식에 따르면 다음과 같은 순서로 작동한다.
-----
32888
82883
88823
-----
2와 3이 서로 교환한 8이 같은 숫자이기 때문에, 서로 다른 숫자와 교환했다고 하면 2와 3의 자리도 교환할 수 있다.
따라서 [교환횟수-1] 을 해 주었다.
lidx+1
로 파라미터를 넘겨서 가장 큰 값 다음부터 교환한다.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 처리
..어디가서 설명은 못 하겠는데 나는 만족하는 풀이 ㅋㅅㅋ