Q. 13428. 숫자 조작(D3)

 

Q. 13428. 숫자 조작(D3)

 

0. 문제

 

D3 난이도의 문제이고, 조합을 이용한 구현 문제라고 생각된다.

9자리 이하의 음이 아닌 정수 N이 주어지고, 두 숫자의 위치를 바꿀 수 있다면

최대값과 최소값을 출력하는 문제이다.

주의해야 할 점은 시작하는 수가 0이 되서는 안된다는 점 이다

---

1. 풀이

 

그냥 조합을 이용해서 풀면 되는 문제인데 어렵게 돌아가려다 삽질을 많이 했다.

먼저 삽질하고 틀린 풀이는 아래와 같다.

1) 최대값, 최소값을 재귀적으로 찾는다

2) 만약 현재 위치의 현재 값이 최소or최대값인 경우 다음 인덱스를 변수로 다시 위 함수를 호출한다.

 

틀린 풀이이다.

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {

	static BufferedReader br;
	static StringBuffer sb = new StringBuffer();
	static StringTokenizer st;
	
	static char[] charN;
	
	static void input() throws IOException {
		charN = br.readLine().toCharArray();
	}
	
	static void pro(int tc) throws Exception{
		
		int min = -1, max = -1;
		if (charN.length == 1) {
			min = charN[0] - '0';
			max = charN[0] - '0';
		} else {
			min = charN[0] == '1' ? findMin(-1, 1) : findMin(0, 0); 
			max = findMax(10, 0);	
		}
		sb.append(String.format("#%d %d %d\n", tc, min, max));
	}
	
	public static int findMin(int biggerThan, int startIdx) {
		
		if (startIdx == charN.length - 1) return Integer.parseInt(String.valueOf(charN));
		int min = 9, minIdx = -1;
		
		for (int i = charN.length - 1; i >= startIdx ; i--) {
			int val = charN[i] - '0';
			if (val < biggerThan) continue;
			if (min > val) {
				min = val;
				minIdx = i;
			}
		}
		if (minIdx == -1) return Integer.parseInt(String.valueOf(charN));
		if (minIdx == startIdx) return findMin(min, startIdx + 1);
		
		int swapIdx = -1;
		for (int i = startIdx; i < charN.length; i++) {
			int val = charN[i] - '0';
			if (val == min) continue;
			else {
				swapIdx = i;
				break;
			}
		}
		if (swapIdx == -1) return Integer.parseInt(String.valueOf(charN));
		return swap(minIdx, swapIdx);
	}
	
	public static int findMax(int smallerThan, int startIdx) {
		
		if (startIdx == charN.length - 1) return Integer.parseInt(String.valueOf(charN));
		int max = -1, maxIdx = -1;
		
		for (int i = charN.length - 1; i >= startIdx ; i--) {
			int val = charN[i] - '0';
			if (val >= smallerThan) continue;
			if (max < val) {
				max = val;
				maxIdx = i;
			}
		}
		if (maxIdx == -1) return Integer.parseInt(String.valueOf(charN));
		if (maxIdx == startIdx) return findMax(max, startIdx + 1);
		
		int swapIdx = -1;
		for (int i = startIdx; i < charN.length; i++) {
			int val = charN[i] - '0';
			if (val == max) continue;
			else {
				swapIdx = i;
				break;
			}
		}
		if (swapIdx == -1) return Integer.parseInt(String.valueOf(charN));
		
		return swap(maxIdx, swapIdx);
	}
	
	public static int swap(int idx1, int idx2) {
	    
		char[] clone = charN.clone();
		char tmp = clone[idx1];
		clone[idx1] = clone[idx2];
		clone[idx2] = tmp;
		
		return Integer.parseInt(String.valueOf(clone));
	}
	
	public static void main(String[] args) throws Exception{
		
//		br = new BufferedReader(new InputStreamReader(System.in));
		br = new BufferedReader(new InputStreamReader(new FileInputStream("res/input.txt")));
		int T = Integer.parseInt(br.readLine());
		for(int tc = 1; tc <= T; tc++) {
			input();
			pro(tc);
		}
        System.out.println(sb);
		
	}

}

그리고 좌절하다가 그냥 조합으로 풀면 되지 않나..하고 조합으로 풀었다.

 

풀이는 아래와 같다.

1) 두 번만 바꾸면 되므로 반복문을 두 번 돌려서 실행한다.

2) 이 때 최소값의 경우 0이 앞에 오면 안되므로 이 경우 다음 루프를 돌도록 한다.

주의해야 할 점은 배열의 경우 매개변수로 배열을 전달하면 주소가 전달된다.

따라서 clone() 함수로 새로 배열을 만들어 위치를 변경해야 한다.

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution {
 
    static BufferedReader br;
    static StringBuffer sb = new StringBuffer();
    static StringTokenizer st;
     
    static char[] charN;
     
    static void input() throws IOException {
        charN = br.readLine().toCharArray();
    }
     
    static void pro(int tc) throws Exception{
         
        int min = Integer.parseInt(String.valueOf(charN)), max = min;
         
        for (int i = 0; i < charN.length - 1; i++) {
            for (int j = i + 1; j < charN.length; j++) {
                max = Math.max(max, swap(i, j));
                if (i == 0 && charN[j] == '0') continue;
                min = Math.min(min, swap(i, j));
            }
        }
         
         
        sb.append(String.format("#%d %d %d\n", tc, min, max));
    }
     
    public static int swap(int idx1, int idx2) {
         
        char[] clone = charN.clone();
        char tmp = clone[idx1];
        clone[idx1] = clone[idx2];
        clone[idx2] = tmp;
         
        return Integer.parseInt(String.valueOf(clone));
    }
     
    public static void main(String[] args) throws Exception{
         
        br = new BufferedReader(new InputStreamReader(System.in));
//      br = new BufferedReader(new InputStreamReader(new FileInputStream("res/input.txt")));
        int T = Integer.parseInt(br.readLine());
        for(int tc = 1; tc <= T; tc++) {
            input();
            pro(tc);
        }
        System.out.println(sb);
         
    }
 
}

---

2. 시간복잡도 계산

 

0) N의 최대값은 999,999,999이다.

1) N의 길이가 최대 9이므로 가능한 모든 조합은 9 * 8 = 72이다.

따라서 제한 시간 관계 없이 충분히 풀 수 있다.