[문제풀이] next permutation(다음순열)과 B9081 단어맞추기

단어 맞추기

---

  🪅. 'next permutation' 알고리즘의 구현에 대해서 알고있어야 한다.
  🪅. 일부분만 정렬하는 내장 메서드에 대해 알고있어야 한다. => 'Arrays.sort(arr, start, end+1);'
  🪅. 배열을 바로 문자열로 만들고 싶을 때 => 'new String(arr);'

❓. next permutation(다음 순열)이란
: 주어진 현재 순열에서 사전순으로 다음에 오는 순열을 구하는 알고리즘을 말한다.

(1). 배열의 뒤에서부터 탐색하며, arr[i-1] < arr[i]를 만족하는 i-1값(가장 큰 인덱스)을 구한다.
  (조건을 만족하는 인덱스가 없을 경우 현재 순열이 마지막 순열이다.)
(2). 다시, 배열의 뒤에서부터 탐색하며 arr[i-1]값보다 큰 값의 인덱스를 구한다.
(3). (1)에서 구한 인덱스(i-1)와 (2)에서 구한 인덱스의 자리를 서로 바꿔준다.
(4). 인덱스 i부터 끝까지 '오름차순 정렬'한다.

  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.Arrays;

  public class B9081_단어맞추기 {
      static int N;
      static String[] words;
      public static void findNext(String word) {
          char[] wordArr = word.toCharArray();
          //test
  //        for(int i = 0; i < wordArr.length; i++) {
  //            System.out.print((int)wordArr[i] + " ");
  //        }
  //        System.out.println();
          //test end

          int idx = wordArr.length-1;
          int remIdx = -1;

          while(idx >= 1) {
              if(wordArr[idx-1] < wordArr[idx]) {
                  remIdx = idx-1;
                  break;
              }
              idx--;

          }
          //다음 단어가 없으면 원본 그대로 출력
          if(remIdx == -1) {
              System.out.println(word);
              return;
          }

          idx = wordArr.length-1;
          for(int i = idx; i > remIdx; i--) {
              if(wordArr[i] > wordArr[remIdx]) {
                  //swap
                  char temp = wordArr[remIdx];
                  wordArr[remIdx] = wordArr[i];
                  wordArr[i] = temp;
                  break;
              }
          }

          //오름차순
          Arrays.sort(wordArr, remIdx+1, wordArr.length);
          System.out.println(new String(wordArr));
      }
      public static void init() throws NumberFormatException, IOException {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          N = Integer.parseInt(br.readLine());
          words = new String[N];

          for(int i = 0; i < N; i++) {
              words[i] = br.readLine();
          }
      }
      public static void main(String[] args) throws NumberFormatException, IOException {
          init();

          for(int i = 0; i < N; i++) {
              findNext(words[i]);
          }
      }
  }

💡. 문제 접근 과정
: 초반에는 각 문자열을 문자배열로 만들고,
문자배열을 각 원소를 숫자 값을 출력하여, 결과를 토대로 규칙을 찾고자 하였으나,
예제 입력으로 나온 예시들만으로는, 숨겨진 테스트케이스를 통과하지 못했다.
이 문제는 next permutation(다음순열) 알고리즘을 알고있어야
무난하게 숨겨진 테스트 케이스까지 통과할 수 있다.