Java 백준 9081 단어 맞추기

백준 링크

https://www.acmicpc.net/problem/9081

---

문제

입력

출력

입출력 예시

 

---

제출한 코드

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();

    static char[] input;

    public static void main(String[] args) throws Exception {
        int t = Integer.parseInt(br.readLine());
        for (int i = 0; i < t; i++) {
            init();
            run();
        }
        System.out.print(sb);
    }

    private static void init() throws Exception {
        input = br.readLine().toCharArray();
    }

    private static void run() {
        int lastIdx = input.length - 1;
        int top = lastIdx;
        
        // 주어진 문자열을 끝에서부터 시작해서 오름차순으로 정렬이 끝나는 위치를 찾기
        while (top > 0 && input[top - 1] >= input[top]) {
            top--;
        }
        
		// 해당 위치보다 큰 숫자 중 가장 작은 숫자와 위치를 스왑
        if (top > 0) {
            int cur = lastIdx;
            
            while (input[top - 1] >= input[cur]) {
                cur--;
            }

            swap(input, top - 1, cur);
			// 해당 위치부터 끝까지 문자열 정렬
            while (top < lastIdx) {
                swap(input, top, lastIdx);
                top++;
                lastIdx--;
            }
        }

        for (char output : input) {
            sb.append(output);
        }
        sb.append("\n");
    }

    private static void swap(char[] input, int i, int j) {
        char temp = input[i];
        input[i] = input[j];
        input[j] = temp;
    }
}

1. 다음 순열 (next permutation) 알고리즘을 활용한다.

2. 입력받은 문자열을 뒤에서 부터 조회한다.

3. 오름차순이 끝나는 부분을 top으로 설정한다.

4. 다시 한번 뒤에서부터 순회하면서 top보다 크면서 가장 작은 값을 찾는다.

5. top과 찾은 값을 스왑해준다.

6. 처음 찾았던 오름차순이 끝나는 위치 뒤부터 정렬을 진행해준다.

 

유사 문제 : https://leetcode.com/problems/next-permutation/description/