백준 2697 자바 - 다음수 구하기 (BOJ 2697 JAVA)

문제 : https://www.acmicpc.net/problem/2697

 

  

  A와 같은 구성에 A보다 큰 수 중 가장 작은 수는 그리디로 해결할 수 있다. 사실 이건 그리디야! 하고 푼건 아니고, 규칙을 찾고보니 그리디 스러운 규칙이었다.ㅋㅋ

 

1. 수를 뒤에서부터 한 자리씩 보면서, 처음으로 수가 이전보다 작아진 지점을 찾는다. 해당 지점을 T라고 하겠다.

 

2. T위치 이전은 그대로 출력한다. 그리고 T 위치를 포함해, 그 이후 위치에 대해 나왔던 숫자들을 몇번씩 나왔는지 카운팅한다.

 

3. T 이후의 위치에 있는 수 중, T에 해당하는 수보다 크면서 가장 작은 수를 찾아 T의 위치에 넣는다.

 

4. 카운팅해둔 값을 가지고, 작은 숫자부터 차례대로 카운팅값 횟수만큼 출력한다.

 

 

 

  설명하기가 애매하니 예시를 들어 설명해보겠다. 예제 입력의 '279134399742'를 보자.

 

1.

  뒤에서부터 차례대로 봤을 때 처음으로 수가 작아지는 부분은 다음과 같이 9->3으로 간 부분이다. 처음으로 숫자가 감소하는 부분에 나왔던 '3'에 해당하는 위치를 T라고 적겠다.

 

2.

T위치와, 그 이후에 나온 숫자를 몇 번씩 나왔는지 카운팅한다. 이하 그림에서 idx 부분이 실제 숫자에 대입된다. 예를들어 idx=9일 때 cnt=2인데, T를 포함한 그 이후의 위치에서 '9'가 2번 나왔다는 의미이다.

 

3.

T미만의 위치에 있는 수는 그대로 출력하면 된다. 그리고 T에 해당하는 숫자(3)를 초과하는 수 중 (즉, 4 이상 중) 가장 먼저 나온 숫자를 T 위치에 넣는다. 그리고 해당 숫자의 cnt를 1 감소시킨다.

 

4.

이후 카운팅해둔 배열을 idx 0부터 차례대로 보면서, 해당 숫자가 나온 횟수만큼 뒤에 붙이면 된다.

 

5.

이 때, 예외사항은 다음과 같다.

 

5.1 모든 숫자가 뒤에서부터 봤을 때 감소하는경우가 없는경우 (e.g. 5433321) -> BIGGEST

5.2 숫자가 1자리인 경우 (e.g. 1) -> BIGGEST

 

 

 

코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/02600/BOJ_2697.java

import java.io.DataInputStream;
import java.io.IOException;

public class Main extends FastInput {
    private static final String BIGGEST = "BIGGEST";

    private String solve(String s) {
        if (s.length() == 1)
            return BIGGEST;

        int[] cnt = new int[10];

        int i = s.length()-2;
        for (; i >= 0; i--) {
            cnt[s.charAt(i+1)-'0']++;
            if (s.charAt(i) < s.charAt(i+1)) {
                cnt[s.charAt(i)-'0']++;
                break;
            }
        }

        if (i == -1)
            return BIGGEST;

        StringBuilder answer = new StringBuilder();
        for (int j = 0; j < i; j++)
            answer.append(s.charAt(j));

        for (int j = (s.charAt(i)-'0')+1; j < cnt.length; j++) {
            if (cnt[j] == 0) continue;
            answer.append((char)('0'+j));
            cnt[j]--;
            break;
        }

        for (int j = 0; j < cnt.length; j++) {
            while (cnt[j]-->0) {
                answer.append((char)('0'+j));
            }
        }
        return answer.toString();
    }

    private void solution() throws Exception {
        int t = nextInt();
        StringBuilder sb = new StringBuilder();
        while (t-->0) {
            String s = nextLine();
            sb.append(solve(s)).append('\n');
        }
        System.out.print(sb);
    }

    public static void main(String[] args) throws Exception {
        initFI();
        new Main().solution();
    }
}

class FastInput {
    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static final int MAX_CHAR_LEN_FOR_NEXT_LINE = 80;
    private static DataInputStream inputStream;
    private static byte[] buffer;
    private static int curIdx, maxIdx;

    protected static void initFI() {
        inputStream = new DataInputStream(System.in);
        buffer = new byte[DEFAULT_BUFFER_SIZE];
        curIdx = maxIdx = 0;
    }

    protected static String nextLine() throws IOException {
        byte[] buf = new byte[MAX_CHAR_LEN_FOR_NEXT_LINE];
        int cnt = 0, c;
        while ((c = read()) != -1) {
            if (c == '\n') {
                if (cnt != 0) break;
                continue;
            }
            buf[cnt++] = (byte)c;
        }
        return new String(buf, 0, cnt);
    }

    protected static int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ') c = read();
        boolean neg = (c == '-');
        if (neg) c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        if (neg) return -ret;
        return ret;
    }

    private static byte read() throws IOException {
        if (curIdx == maxIdx) {
            maxIdx = inputStream.read(buffer, curIdx = 0, DEFAULT_BUFFER_SIZE);
            if (maxIdx == -1) buffer[0] = -1;
        }
        return buffer[curIdx++];
    }
}