[백준] 단어나누기 - 1251번

단어 나누기

2 초	128 MB	13483	5760	4966	46.590%

문제

알파벳 소문자로 이루어진 단어를 가지고 아래와 같은 과정을 해 보려고 한다.

먼저 단어에서 임의의 두 부분을 골라서 단어를 쪼갠다. 즉, 주어진 단어를 세 개의 더 작은 단어로 나누는 것이다. 각각은 적어도 길이가 1 이상인 단어여야 한다. 이제 이렇게 나눈 세 개의 작은 단어들을 앞뒤를 뒤집고, 이를 다시 원래의 순서대로 합친다.

예를 들어,

• 단어 : arrested
• 세 단어로 나누기 : ar / rest / ed
• 각각 뒤집기 : ra / tser / de
• 합치기 : ratserde

단어가 주어지면, 이렇게 만들 수 있는 단어 중에서 사전순으로 가장 앞서는 단어를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 영어 소문자로 된 단어가 주어진다. 길이는 3 이상 50 이하이다.

출력

첫째 줄에 구하고자 하는 단어를 출력하면 된다.

예제 입력 1 복사

mobitel

예제 출력 1 복사

bometil

알고리즘 분류

• 구현
• 문자열
• 브루트포스 알고리즘
• 정렬

코드

package 단어나누기;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);

    public static void main(String[] args) throws Exception {
        // 입력 단어 읽기
        String word = br.readLine();
        // 단어 길이 저장
        int wordLength = word.length();

        // 가능한 모든 단어 조합 저장할 리스트 생성
        List<String> possibleWords = new ArrayList<>();

        // 단어를 2개의 부분으로 나누는 모든 경우의 수를 탐색
        for (int splitPosition1 = 1; splitPosition1 < wordLength; splitPosition1++) {
            for (int splitPosition2 = splitPosition1 + 1; splitPosition2 < wordLength; splitPosition2++) {
                // 단어를 3개의 부분으로 나누기
                String firstPart = word.substring(0, splitPosition1);
                String secondPart = word.substring(splitPosition1, splitPosition2);
                String thirdPart = word.substring(splitPosition2);

                // 각 부분을 뒤집기
                String reversedFirstPart = new StringBuilder(firstPart).reverse().toString();
                String reversedSecondPart = new StringBuilder(secondPart).reverse().toString();
                String reversedThirdPart = new StringBuilder(thirdPart).reverse().toString();

                // 뒤집은 부분들을 합쳐 새로운 단어 생성
                String newWord = reversedFirstPart + reversedSecondPart + reversedThirdPart;

                // 가능한 단어 리스트에 추가
                possibleWords.add(newWord);
            }
        }

        // 가능한 단어들을 사전순으로 정렬
        Collections.sort(possibleWords);

        // 사전순으로 가장 앞서는 단어 출력
        System.out.println(possibleWords.get(0));
        br.close();

    }

}

설명

의문

2개의 for loop의 splitPosition1이 처음 1이 할당되는 이유와 splitPosition2가 splitPosition1+1이 되는 이유!

1. 2개의 for 루프 역할:

이 중첩된 for 루프는 주어진 단어를 2개의 부분으로 나누는 모든 경우의 수를 탐색합니다. 각 경우의 수는 단어 길이에 따라 다릅니다.

2. splitPosition1 초기화:

• splitPosition1은 단어를 나누는 첫 번째 위치를 나타내는 변수입니다.
• 첫 번째 for 루프에서 splitPosition1은 1로 초기화됩니다. 즉, 단어의 첫 번째 문자는 항상 첫 번째 부분에 포함됩니다.

3. splitPosition2 초기화:

• splitPosition2는 단어를 나누는 두 번째 위치를 나타내는 변수입니다.
• 두 번째 for 루프에서 splitPosition2는 splitPosition1 + 1로 초기화됩니다. 즉, 두 번째 부분은 첫 번째 부분의 길이보다 적어도 1개 이상 길어야 합니다.
• 이러한 초기화는 첫 번째 부분이 항상 적어도 1개의 문자를 포함하고, 두 번째 부분은 적어도 1개 이상의 문자를 포함하도록 합니다.

4. 예시 설명:

• 예를 들어, 단어 "apple"을 생각해 보세요.
  • 첫 번째 for 루프가 실행되면 splitPosition1은 1, 2, 3으로 순차적으로 증가합니다.
  • 각 splitPosition1 값에 대해 두 번째 for 루프가 실행되어 splitPosition2는 splitPosition1 + 1부터 단어 길이까지 순차적으로 증가합니다.
  • 이렇게 모든 경우의 수를 탐색하여 가능한 모든 단어 조합을 생성합니다.

5. 중요성:

• 이러한 초기화 방식은 모든 경우의 수를 포괄적으로 탐색하는 데 중요합니다.
• 만약 splitPosition1을 0으로 초기화한다면, 첫 번째 부분이 빈 문자열이 될 수 있는 경우가 발생하여 오류가 발생할 수 있습니다.
• 또한, splitPosition2를 splitPosition1와 같거나 작게 초기화한다면, 두 번째 부분이 항상 빈 문자열이 될 수 있는 경우가 발생하여 원하는 결과를 얻지 못할 수 있습니다.

결론:

splitPosition1의 초기화는 1, splitPosition2의 초기화는 splitPosition1 + 1로 설정하는 것이 모든 경우의 수를 포괄적으로 탐색하고 올바른 결과를 얻는 데 필수적입니다.