SW Expert 13428 JAVA : 숫자 조작

문제

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

SW Expert Academy

 

풀이 예상

자릿 수 마다 개수를 저장할 배열을 만들어 저장하고

앞쪽에서 부터 바꿔야 할 숫자를 저장한 후, 바꿔야될 숫자면 뒤쪽에서부터 바꿀 숫자를 찾는다.

 

 

 

풀이방법 (접근 방법 & 시간복잡도)

ex) 142857 - 작은 숫자 찾기

 

1. 각 자리의 숫자를 배열에 저장한다.

nums[0]	nums[1]	nums[2]	nums[3]	nums[4]	nums[5]	nums[6]	nums[7]	nums[8]	nums[9]
0	1	1	0	1	1	0	1	1	0

 

 

2. 앞자리 부터 순회하면서 바꿔야할 숫자인지 판별한다.

   2-1. 0번째자리 - 1

    nums[1]을 -1 해주고, 바꿔야 할 숫자가 아니기 때문에 패스

   2-2. 1번째 자리 - 4 

   nums[4]을 -1 해주고 nums[0]~ nums[3]까지 순회하며 바꿀 숫자가 있는지 찾아본다.

   => nums[2] 에 값이 있으므로 2라는 값을 changeNum 에 저장후 탈출, changeDigit = 1(바꿔야 할 숫자)

 

3. 숫자를 바꿔준다. changeNumber()

  3-1. 뒷자리부터 순회하면서 changeNum 의 자리를 찾아낸다.

    기존 값을 빼주고, 새 값을 더해준다. 

 

 

시간복잡도 => O(N)

각 자리마다 최대 9번 비교하고, 바꿀때는 한 번의 반복을 통해 바꿀 수 있다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Solution {
    static int[] nums;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args)throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for (int t = 1; t <= T; t++) {
            String str = br.readLine();

            sb.append("#").append(t).append(" ");
            small(str);
            big(str);
            sb.append("\n");
        }
        System.out.println(sb);

    }
    static void small (String str) {
        nums = new int[10];
        for (int i = 0; i < str.length(); i++) {
            nums[str.charAt(i)-'0']++;
        }

        int changeDigit = 100;
        int changeNum = 100;

        for (int i = 0; i < str.length(); i++) {
            int number = Integer.parseInt(str.charAt(i)+"");
            nums[number]--;

            int startNum = 0;
            changeNum = 100;
            if(i == 0) {
                startNum = 1;
            }

            for (int j = startNum; j < number; j++) {
                //작은 숫자를 찾는다.
                if(nums[j] > 0) {
                    changeNum = j;
                    break;
                }
            }
            if(changeNum!=100) {
                changeDigit =i;
                break;
            }
        }

        changeNumber(str, changeNum, changeDigit);

    }
    static void big (String str) {
        nums = new int[10];
        for (int i = 0; i < str.length(); i++) {
            nums[str.charAt(i)-'0']++;
        }

        int changeDigit = 100;
        int changeNum = 100;

        for (int i = 0; i < str.length(); i++) {
            int number = Integer.parseInt(str.charAt(i)+"");
            nums[number]--;

            changeNum = 100;


            for (int j = 9; j > number; j--) {
                //큰 숫자를 찾는다.
                if(nums[j] > 0) {
                    changeNum = j;
                    break;
                }
            }
            if(changeNum!=100) {
                changeDigit =i;
                break;
            }
        }
        changeNumber(str, changeNum, changeDigit);

    }
    static void changeNumber(String str, int changeNum, int changeDigit){
        double strNum = Double.parseDouble(str);
        if(changeDigit!= 100) {
            //자리를 바꿔준다.
            for (int i = str.length()-1; i >= 0; i--) {
                if(Integer.parseInt(str.charAt(i)+"") == changeNum) {
                    //기존 값 빼주기
                    strNum -= Math.pow(10, str.length()-changeDigit-1) * str.charAt(changeDigit);
                    strNum -= Math.pow(10, str.length()-i-1) * str.charAt(i);

                    //새 값 더해주기
                    strNum += Math.pow(10, str.length()-changeDigit-1) * str.charAt(i);
                    strNum += Math.pow(10, str.length()-i-1) * str.charAt(changeDigit);

                    break;
                }
            }

        }
        sb.append((int) strNum).append(" ");

    }
}

 

결과