단어 나누기
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
로 설정하는 것이 모든 경우의 수를 포괄적으로 탐색하고 올바른 결과를 얻는 데 필수적입니다.
'여러가지 > 알고리즘 & 자료구조' 카테고리의 다른 글
[백준] 슈퍼마리오 - 2851번 (0) | 2024.06.13 |
---|---|
[백준] 암호 만들기 - 1759번 (0) | 2024.06.13 |
[백준] 지각 - 10419번 (1) | 2024.06.12 |
[백준] 좋은 암호 - 2061번 (0) | 2024.06.12 |
[백준] 타임머신 - 1440번 (1) | 2024.06.12 |