백준 2697번
https://www.acmicpc.net/problem/2697

문제

---

생각하기

---

• 그리디, 문자열 문제이다.

동작

입력받는 정숫값을 char형태의 배열로 전환한다.

전환 후 뒤에서부터 순서대로 진행하면서 i 값과 i - 1의 값을 비교할 때 i - 1이 i 값보다 작은 값이 나오면 거기서 중단하고 큰 수를 만들면 된다.

예를 들어 279134399742 이 예시일 때
2 -> 4 -> 7 -> 9 -> 9 순서로 진행하다가 3을 만나면 중단된다.

2부터 9까지는 커지는 숫자이므로 이들의 값은 어떻게 변경해도 큰 값을 만들 수 없기 때문이다.

그러다가 3을 만나면서 진행되는 숫자보다 작은 값을 만나면 해당 값과 가장 작은 차이가 나는 값과 위치를 변경했을 때

해당 숫자로 만들 수 있는 큰 값 중 가장 작은 수가 된다.

        for (int i = N - 1; i >= 1; i--) {
            int point = chArr[i] - '0';

            // point보다 작은 값을 만나면 중단
            if (chArr[i - 1] - '0' < point) {
                int target = chArr[i - 1] - '0';

                StringBuilder build = new StringBuilder();
                for (int j = i; j < N; j++) {
                    build.append(chArr[j]);
                }

                char[] tempChArr = build.toString().toCharArray();
                Arrays.sort(tempChArr);
                int len = tempChArr.length;

                // chArr[i - 1]보다 큰 값 나오면 바로 교환
                for (int j = 0; j < len; j++) {
                    if (tempChArr[j] - '0' > target) {
                        char temp = chArr[i - 1];
                        chArr[i - 1] = tempChArr[j];
                        tempChArr[j] = temp;
                        break;
                    }
                }

                for (int j = 0; j <= i - 1; j++) {
                    sb.append(chArr[j]);
                }

                for (int j = 0; j < len; j++) {
                    sb.append(tempChArr[j]);
                }
                break;
            }
        }

결과

코드

---

Java

import java.io.*;
import java.util.Arrays;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static final String BIG = "BIGGEST";

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            bw.write(solve());
        }

        bw.close();
    } // End of main()

    private static String solve() throws IOException {
        StringBuilder sb = new StringBuilder();

        String str = br.readLine();
        char[] chArr = str.toCharArray();
        int N = str.length();

        for (int i = N - 1; i >= 1; i--) {
            int point = chArr[i] - '0';

            // point보다 작은 값을 만나면 중단
            if (chArr[i - 1] - '0' < point) {
                int target = chArr[i - 1] - '0';

                StringBuilder build = new StringBuilder();
                for (int j = i; j < N; j++) {
                    build.append(chArr[j]);
                }

                char[] tempChArr = build.toString().toCharArray();
                Arrays.sort(tempChArr);
                int len = tempChArr.length;

                // chArr[i - 1]보다 큰 값 나오면 바로 교환
                for (int j = 0; j < len; j++) {
                    if (tempChArr[j] - '0' > target) {
                        char temp = chArr[i - 1];
                        chArr[i - 1] = tempChArr[j];
                        tempChArr[j] = temp;
                        break;
                    }
                }

                for (int j = 0; j <= i - 1; j++) {
                    sb.append(chArr[j]);
                }

                for (int j = 0; j < len; j++) {
                    sb.append(tempChArr[j]);
                }
                break;
            }
        }

        if (sb.length() == 0) {
            sb.append(BIG);
        }
        sb.append('\n');

        return sb.toString();
    } // End of solve()
} // End of Main class

Kotlin

import java.io.BufferedReader
import java.io.File

// input
private var br = System.`in`.bufferedReader()

// variables
private const val BIG = "BIGGEST"

fun main() {
    val bw = System.out.bufferedWriter()

    var t = br.readLine().toInt()
    while (t-- > 0) {
        bw.write(solve())
    }

    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    val str = br.readLine()
    val n = str.length
    val chArr = str.toCharArray()
    val numBuilder = StringBuilder()

    for (i in n - 1 downTo 1) {
        // i와 i + 1을 비교해서 i + 1이 더 작은 값일 경우 중단
        val point = Character.getNumericValue(chArr[i])
        var next = Character.getNumericValue(chArr[i - 1])

        if (point > next) {
            // next와 차이가 가장 적게나는 값이랑 교환하기
            val tempArr = str.substring(i, n).toCharArray()
            tempArr.sort()
            val tempArrLen = tempArr.size

            for (j in 0 until tempArrLen) {
                if (Character.getNumericValue(tempArr[j]) > next) {
                    // next보다 가장 작은 차이의 큰 값 발견하면 swap
                    val temp = tempArr[j]
                    tempArr[j] = chArr[i - 1]
                    chArr[i - 1] = temp
                    break
                }
            }

            for (j in 0 .. i - 1) {
                numBuilder.append(chArr[j])
            }

            tempArr.forEach {
                numBuilder.append(it)
            }
            break
        }
    }

    if (numBuilder.isEmpty()) {
        sb.append(BIG)
    } else {
        sb.append(numBuilder.toString())
    }

    sb.append('\n')
    return sb.toString()
} // End of solve()