백준 9081번 단어 맞추기 [JAVA]

문제

BEER라는 단어를 이루는 알파벳들로 만들 수 있는 단어들을 사전 순으로 정렬하게 되면

와 같이 된다. 이러한 순서에서 BEER 다음에 오는 단어는 BERE가 된다. 이와 같이 단어를 주면 그 단어를 이루는 알파벳들로 만들 수 있는 단어들을 사전 순으로 정렬할 때에 주어진 단어 다음에 나오는 단어를 찾는 프로그램을 작성하시오.

 

입력

입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 하나의 단어가 한 줄로 주어진다. 단어는 알파벳 A~Z 대문자로만 이루어지며 항상 공백이 없는 연속된 알파벳으로 이루어진다. 단어의 길이는 100을 넘지 않는다.

 

출력

각 테스트 케이스에 대해서 주어진 단어 바로 다음에 나타나는 단어를 한 줄에 하나씩 출력하시오. 만일 주어진 단어가 마지막 단어이라면 그냥 주어진 단어를 출력한다.

 

예제

풀이 방법

주어진 단어 다음에 나오는 단어를 찾는 문제였습니다.

 

처음에는 가능한 단어들을 다 만들어 놓고 정렬한 뒤, 주어진 단어의 다음 단어를 출력해주도록 구현했지만, 단어의 길이가 최대 99이므로 시간초과가 발생했습니다.

 

그래서 두번째로 구현한 방법이 

1 ) 단어 맨뒤에서부터 확인하면서 감소하는 부분 찾기

2 ) 다시 단어 맨뒤에서부터 확인하면서 감소하는 부분보다 큰 부분 찾기

3 ) 둘 위치 바꿔주기

4 ) 1)의 위치 뒷 부분 정렬

입니다.

 

예시)

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
 
public class Main_BJ_9081_단어맞추기 {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int T = Integer.parseInt(br.readLine());
        
        for(int i=0;i<T;i++) {
            char [] word = br.readLine().toCharArray();
            
            int index=-1, index2=0;
            char temp;
        
            for(int j=word.length-1;j>0;j--) {
                if(word[j-1]<word[j]) {
                    index=j-1; break;
                }
            }
            
            if(index==-1) {
                for(int j=0;j<word.length;j++) sb.append(word[j]);
                sb.append("\n");
            }
            else {
                for(int j=word.length-1;j>=0;j--) {
                    if(word[index]<word[j]) {
                        index2=j; break;
                    }
                }
                temp = word[index];
                word[index] = word[index2];
                word[index2] = temp;
                
                Arrays.sort(word,index+1, word.length);
                
                for(int j=0;j<word.length;j++) sb.append(word[j]);
                sb.append("\n");
            }
            
        }
        System.out.println(sb.toString());
    }
}