[PS] BOJ9081 단어 맞추기 ( string ) with JAVA

 

9081번: 단어 맞추기

 

 

◎ 문제풀이 

 

사전 순서로 할 때, 주어진 단어의 알파벳으로 구성된 주어진 단어의 다음 단어를 찾는 문제이다.

 

처음에는 DFS로 풀었다.

 

DFS로 사전순서대로 탐색하다가 주어진 단어의 다음 단어를 찾는 식이었다. 그런데 이는 메모리 초과가 발생했다. DFS를 하려면 방문처리를 위한 배열도 생성해야 하는데, 그런거 없이 오로지 문자열만을 조작하여 문제를 풀어야 했다. 어떠한 알고리즘이 필요한 거였는데, 잘 몰라서 구글링을 하였다. 원리는 생각보다 복잡했다.

 

사전순의 의미는 아래와 같다.

 

 

 

 

A를 0으로 했을때, 오름차순으로 배열되면 사전에서 가장 앞에 있는 단어이다. 

 

그럼 사전 순서로 가장 뒤에 있는 단어는 무엇일까?

 

 

 

 

내림차순으로 배열되면 가장 뒤에 있는 단어이다. 

 

그러므로 사전 앞에서 뒤로 갈수록 오름차순에서 내림차순으로 변하는 것이다.

이때 변화는 가장 뒤에서부터 시작된다. 

 

 

그럼 예시를 하나 더 들어 보겠다.

 

 

 

 

SHUTTLE 이라는 단어이다. 

사전순으로 SHUTTLE의 다음 단어를 찾아보자.

 

가장 뒤인 E부터 하나씩 올라가면 계속 증가한다. 이는 사전순에서 가장 뒤에 있다는 의미이다. 그러다가 U에서 H로 갈때 처음으로 감소한다. 그럼 감소가 되는 지점인 H를 다음 문자로 바꾸어 주어야 다음 단어가 된다. 

 

S, H를 제외한 알파벳 중에 H 바로 다음에 오는 알파벳은 L이다. 

 

 

H자리는 L이 차지한다. 

 

우리가 원하는 단어는 SHUTTLE의 '바로 다음' 단어이다. L이 새롭게 H자리에 왔을때 사전 순으로 가장 첫 단어는 남은 알파벳이 오름차순으로 정렬되었을 때이다.

 

 

정리하면,

 

1) 주어진 단어의 가장 뒤에서부터 탐색하여 내림차순을 검사한다.

2) 단어 전체가 내림차순이면 사전 가장 뒤에 있는 단어이므로 바로 답으로 출력한다.

3) 특정 알파벳에서 내림차순이 깨지면, 해당 알파벳 위치에 그 알파벳의 다음 알파벳을 위치시킨다.

4) 남은 알파벳들을 오름차순으로 정렬하면 주어진 단어의 바로 다음 단어가 된다. 

 

 

◎ 코드

package org.example.string;


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

//BOJ9081 단어 맞추기
public class String6 {

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

        while(t-- > 0){
            String value = br.readLine();
            char[] str = value.toCharArray();
            int[] alphabets = new int['Z'-'A'+1];
            StringBuilder sb = new StringBuilder();

            int index = -1;
            
            // 내림차순으로 정렬되어 있는지 확인
            for(int i = str.length-1;i>0;i--){
                if(str[i-1] < str[i]) { // 내림차순이 깨지는 부분
                    index = i-1;
                    break;
                }
            }
            
            // 내림차순이 깨지는 부분이 있는 경우
            if(index != -1){
                // 깨지는 부분의 앞부분은 미리 빌더에 넣어놓기
                for(int i=0;i<index;i++){
                    sb.append(str[i]);
                }

                // 깨진 부분부터 알파벳테이블에 단어 수 카운트하기
                for(int i = index; i<str.length;i++){
                    alphabets[getInt(str[i])]++;
                }
                
                // 깨진 부분 알파벳의 다음 알파벳 구하기
                int pointer = getInt(str[index]);
                for(int i = pointer+1;i<alphabets.length;i++){
                    if(alphabets[i] > 0){
                        sb.append(getChar(i)); // 다음 알파벳 빌더에 넣기
                        alphabets[i]--;
                        break;
                    }
                }

                // 나머지 알파벳은 오름차순으로 빌더에 넣기
                for(int i=0;i<alphabets.length;i++){
                    for(int j=0;j<alphabets[i];j++){
                        sb.append(getChar(i));
                    }
                }

                // 출력
                System.out.println(sb.toString());

            }
            // 단어 전체가 내림차순으로 구성된 경우
            else {
                System.out.println(value);
            }

        }
    }


    public static char getChar(int value){
        return (char)(value+'A');
    }

    public static int getInt(char value){
        return value-'A';
    }
}