[백준] 9081: 단어 맞추기 - JAVA

in Algorithm on 수학

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

풀이

C++에 있는 next permutation 함수를 구현하는 문제이다.

어떤 문자가 주어지면 그 문자의 알파벳들로 만들 수 있는 문자들 중 처음 주어진 문자의 다음에 올 문자를 찾는 문제였다.

조합으로 모든 경우를 만들어 set에 넣는 방식으로 구현하였는데 메모리초과로 실패했다.

next permutaion이란 방법을 찾아 구현해보았다.

1. 뒤에서부터 탐색하여 증가하지 않는 첫번째 인덱스를 찾는다.
2. 다시 뒤에서부터 탐색하여 찾은 인덱스의 값보다 처음으로 큰 값이 나오는 인덱스를 찾는다.
3. 두 인덱스의 값을 바꾸고 인덱스 뒤 부분을 정렬하여 붙인다.

따라서, 주어진 단어를 int배열로 만들어 구현했다.

뒤에서부터 탐색해 값이 감소하는 인덱스를 찾았고 탐색하면서 list에 숫자를 넣었다.

찾은 인덱스의 값보다 큰 값이 나오는 인덱스를 찾아 바꿔주었고,

list를 정렬하여 단어를 완성시켰다.

메모리: 14044KB

시간: 120ms

언어: Java 11

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        for (int tc = 0; tc < T; tc++) {
            String word = br.readLine();
            int[] arr = new int[word.length()];
            for (int i = 0; i < word.length(); i++) {
                arr[i] = word.charAt(i) - 65;
            }

            ArrayList<Integer> list = new ArrayList<>();
            int idx = -1;
            for (int i = arr.length - 1; i > 0; i--) {
                list.add(arr[i]);
                if (arr[i] > arr[i - 1]) {
                    idx = i - 1;
                    break;
                }
            }

            if (idx == -1) {
                sb.append(word).append("\n");
            } else {
                for (int i = 0; i < list.size(); i++) {
                    if (list.get(i) > arr[idx]) {
                        list.add(arr[idx]);
                        arr[idx] = list.get(i);
                        list.remove(i);
                        break;
                    }
                }

                Collections.sort(list);

                for (int i = 0; i <= idx; i++) {
                    sb.append((char) (arr[i] + 65));
                }
                for (Integer i : list) {
                    sb.append((char) (i + 65));
                }
                sb.append("\n");
            }
        }

        System.out.println(sb.toString());
    }

}