💡 문제
비슷한 단어 (https://www.acmicpc.net/problem/2179)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.
📝 선행 개념
주어진 문제를 해결하기 위해 다양한 자료 구조와 알고리즘을 사용할 수 있다.
해당 문제에서는 해시맵(HashMap)과 배열을 사용하여 문제를 해결하였으며 아래는 해당 문제를 해결하는 데 사용된 자료 구조와 알고리즘에 대한 설명입니다.
자료 구조
- 해시맵 (HashMap): 단어를 키로, 해당 단어의 입력 순서를 값으로 저장합니다. 이를 통해 단어의 입력 순서를 기억할 수 있습니다.
- 배열 : 입력된 단어들을 저장합니다. 이를 통해 단어 쌍을 비교할 수 있습니다.
알고리즘
- 문자열 비교:
- 각 단어 쌍에 대해 최대 접두사 길이를 계산합니다.
- 이중 반복문 (Nested Loop):
- 모든 단어 쌍을 비교하여 최대 접두사 길이를 찾습니다.
- 접두사 길이 계산 함수:
- 두 문자열을 비교하여 최대 접두사 길이를 계산합니다.
그리고 문제 풀때는 scanner 보다는 BufferedReader를 사용한다.
BufferedReader는 Scanner보다 빠르고 효율적으로 입력을 처리할 수 있어서 사용하고 있습니다.
🤓 문제 풀이
가장 비슷한 두 단어를 찾는 문제 각 단어 쌍을 비교하여 가장 긴 공통 접두사를 가지는 두 단어 찾기
- 입력된 영단어들 중에서 두 단어씩 조합하여 모든 가능한 접두사를 비교합니다.
- 접두사의 길이가 최대인 경우를 찾아 두 단어를 출력합니다.
- 단어를 입력받을 때마다 순서를 기억하여 접두사의 길이가 최대인 경우를 우선적으로 선택합니다.
1) 코드 (처리속도 빠름)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
// 두 단어의 공통 접두사의 길이를 계산하는 함수
private static int wordLength(String word1, String word2){
int minLength = Math.min(word1.length(), word2.length());
for (int i=0; i<minLength; i++){
if (word1.charAt(i) != word2.charAt(i)){
return i;
}
}
return minLength;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 첫 줄에서 단어의 개수 'n' 입력 받기
int n = Integer.parseInt(br.readLine());
String[] words = new String[n];
// 단어 입력 받기
// 다음 n개의 줄에서 각 단어를 배열에 저장
for (int i=0; i<n; i++){
words[i] = br.readLine();
}
int maxPrefixLength = -1;
String resultWord1 = "";
String resultWord2 = "";
// 모든 단어 쌍에 대해 접두사 길이를 계산
// 이중 루프를 사용하여 모든 단어 쌍을 비교하고, 접두사 길이가 최대인 경우를 추적
for(int i=0; i<n; i++){
for (int j=i+1; j<n; j++){
int prefixLength = wordLength(words[i], words[j]);
if (prefixLength > maxPrefixLength){
maxPrefixLength = prefixLength;
resultWord1 = words[i];
resultWord2 = words[j];
}
}
}
// 결과출력
System.out.println(resultWord1);
System.out.println(resultWord2);
}
}🔍 부분 설명
- wordLength 함수:
- 두 단어의 최소 길이만큼 문자를 비교합니다.
- 문자가 다르면 현재 인덱스를 반환합니다.
- 모든 문자가 동일하다면 최소 길이를 반환합니다.
private static int wordLength(String word1, String word2){
int minLength = Math.min(word1.length(), word2.length());
for (int i=0; i<minLength; i++){
if (word1.charAt(i) != word2.charAt(i)){
return i;
}
}
return minLength;
}- 메인 함수:
- BufferedReader를 사용하여 입력을 받습니다.
- 첫 줄에서 단어의 개수 **n**을 읽어옵니다.
- 다음 **n**개의 줄에서 각 단어를 배열에 저장합니다.
- 이중 루프를 사용하여 모든 단어 쌍을 비교하고, 접두사 길이가 최대인 경우를 추적합니다.
- 접두사 길이가 최대인 두 단어를 출력합니다.
for(int i=0; i<n; i++){
for (int j=i+1; j<n; j++){
int prefixLength = wordLength(words[i], words[j]);
if (prefixLength > maxPrefixLength){
maxPrefixLength = prefixLength;
resultWord1 = words[i];
resultWord2 = words[j];
}
}
}
이 코드는 문제에서 요구한 대로 가장 긴 접두사를 가지는 두 단어를 찾아내고, 접두사 길이가 최대인 경우가 여러 개일 때는 입력 순서를 고려하여 첫 번째로 찾은 쌍을 출력합니다.
📚 풀이 보완
- ...
2) 코드
자료 구조로는 해시맵을 사용하여 각 단어와 해당 단어의 인덱스를 저장할 수 있습니다. 이를 통해 단어의 입력 순서를 유지하면서 문제를 해결할 수 있습니다.
이 코드는 입력된 단어들 중 가장 비슷한 두 단어를 찾아내는 프로그램을 구현한 것입니다. 처음에 입력된 순서대로 단어를 처리하며, 각 단어와 이전까지 입력된 단어들과의 접두사를 비교하여 최대 접두사의 길이를 찾습니다. 최대 접두사의 길이가 여러 개일 경우에는 입력된 순서대로 우선순위를 결정하여 결과를 출력합니다.
- 단어의 개수를 입력받고, 단어와 해당 단어의 인덱스를 저장할 **HashMap**을 생성합니다.
- 각 단어를 입력받으면서 해당 단어와 이전에 입력된 모든 단어들의 최대 접두사 길이를 계산합니다.
- 최대 접두사 길이가 갱신될 때마다 그에 따른 첫 번째와 두 번째 단어를 업데이트합니다.
- 모든 입력이 완료되면 첫 번째와 두 번째 단어를 출력합니다.
public class Main {
// 두 단어의 최대 접두사 길이를 계산하는 함수
private static int getWordLength(String word1, String word2){
// 두 단어 중 짧은 길이
int minLength = Math.min(word1.length(), word2.length());
// 최대 접두사 길이
int maxLength = 0;
// 단어의 각 문자를 비교하여 최대 접두사 길이를 계산
for (int i = 0; i < minLength; i++){
if (word1.charAt(i) == word2.charAt(i)){
maxLength++; // 단어가 같으면 접두사 길이 증가
}else{
break; // 단어가 다르면 비교 종료
}
}
return maxLength;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 단어의 개수 입력 받기
int n = Integer.parseInt(br.readLine());
// 단어와 인덱스를 저장할 해시맵 (단어를 키로, 인덱스를 값으로 저장)
Map<String, Integer> wordIndex = new HashMap<>();
String[] words = new String[n]; // 단어를 저장할 배열
// 단어를 배열에 저장하여 각 단어 쌍에 대해 접두사 길이를 계산
for (int i = 0; i < n; i++){
// 단어 입력 받기
words[i] = br.readLine();
// 단어와 해당 단어의 인덱스 저장
wordIndex.put(words[i], i);
}
// 가장 비슷한 두 단어를 저장할 변수
String firstWord = ""; // 첫 번째 단어
String secondWord = ""; // 두 번째 단어
int maxPrefixLength = 0; // 최대 접두사의 길이
// 모든 단어 쌍에 대해 최대 접두사 길이 계산
for (int i = 0; i < n; i++){
for (int j = i + 1; j < n; j++){
// 현재 단어와 그 다음 단어들에 대해 접두사 길이 계산
int getPrefixLength = getWordLength(words[i], words[j]);
// 현재 최대 길이보다 크면 갱신
if (getPrefixLength > maxPrefixLength){
maxPrefixLength = getPrefixLength;
firstWord = words[i];
secondWord = words[j];
}
}
}
// 결과 출력
System.out.println(firstWord); // 첫 번째 단어 출력
System.out.println(secondWord); // 두 번째 단어 출력
}
}🔍 부분 설명
최대 접두사 길이를 계산하는 부분에서 잘못된 점이 있었다. 반복해서 비교하기 때문에 발생
아래는 수정한 내용이다.
- 단어를 배열에 저장하여 각 단어 쌍에 대해 접두사 길이를 계산하도록 변경했습니다.
- **wordIndex**를 유지하여 동일 단어가 반복되지 않도록 했습니다.
- 모든 단어 쌍에 대해 비교하기 위해 이중 for 루프를 사용했습니다.
1. 입력 처리 및 초기화
- 'n' 은 입력된 단어의 개수입니다.
- 'wordIndex'는 단어와 해당 단어의 입력 순서를 저장합니다.
- words 배열은 입력된 단어를 저장합니다.
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
Map<String, Integer> wordIndex = new HashMap<>();
String[] words = new String[n];
2. 단어 입력 및 저장
- 각 단어를 입력받아 words 배열과 wordIndex 해시맵에 저장합니다.
for (int i = 0; i < n; i++){
words[i] = br.readLine();
wordIndex.put(words[i], i);
}
3. 최대 접두사 길이 계산
- 이중 for 루프를 사용하여 모든 단어 쌍을 비교합니다.
- getWordLength 함수를 호출하여 두 단어의 접두사 길이를 계산합니다.
- 최대 접두사 길이를 갱신하고, 해당 단어들을 'firstWord'와 'secondWord' 에 저장합니다.
String firstWord = "";
String secondWord = "";
int maxPrefixLength = 0;
for (int i = 0; i < n; i++){
for (int j = i + 1; j < n; j++){
int getWordLength = getWordLength(words[i], words[j]);
if (getPrefixLength > maxPrefixLength){
maxPrefixLength = getPrefixLength;
firstWord = words[i];
secondWord = words[j];
}
}
}
4. 접두사 길이 계산 함수
- 단어 중 짧은 길이만큼 비교하며, 같은 문자가 나올 때마다 maxLength를 증가시킵니다. 다른 문자가 나오면 비교를 중단
private static int getWordLength(String word1, String word2){
int minLength = Math.min(word1.length(), word2.length());
int maxLength = 0;
for (int i = 0; i < minLength; i++){
if (word1.charAt(i) == word2.charAt(i)){
maxLength++;
} else {
break;
}
}
return maxLength;
}
위 코드는 자료 구조, 문자열, 정렬, 해시를 사용한 집합과 맵을 이용하여 문제를 해결합니다. 단어의 비교와 접두사 길이 계산을 통해 최적의 두 단어를 찾고, 입력 순서를 고려하여 정확한 결과를 출력합니다.
📍 Plus+
두 클래스는 서로 로직 처리 속도 차이점 설명 및 이모저모 ~..~
두 클래스 첫번째 코드와 두번째 코드는 주어진 문제를 해결하는 방식에 있어서 약간의 차이가 있습니다. 두 코드 모두 동일한 문제를 해결하려고 하지만, 접근 방식과 로직 처리 속도에 있어 약간의 차이가 있습니다.
1번 이 클래스는 이중 루프를 사용하여 모든 단어 쌍을 비교하고 접두사 길이를 계산합니다.
2번 이 클래스는 단어를 저장할 때 인덱스를 함께 저장하는 해시맵을 사용하여 입력된 순서를 기억하고, 이중 루프를 사용하여 모든 단어 쌍을 비교합니다. 그러나 실제로 비교하는 방식과 로직은 1번 클래스와 유사합니다.
차이점 및 성능 분석
1. 입력 순서 저장: BOJ_2179_비슷한단어_hash 클래스는 해시맵을 사용하여 단어의 입력 순서를 저장합니다. 이는 단어의 비교 시 순서를 고려할 수 있게 합니다. 그러나 현재 코드에서는 입력 순서를 고려한 추가적인 로직이 없으므로 두 클래스 모두 동일한 방식으로 단어를 비교합니다.
2. 접두사 길이 계산: 두 클래스 모두 접두사 길이 계산 함수(wordLength 및 getWordLength)를 사용하여 두 단어의 접두사 길이를 계산합니다.
3. 성능: 두 클래스 모두 이중 루프를 사용하여 모든 단어 쌍을 비교하므로 시간 복잡도는 O(n^2)입니다. 단어의 최대 길이가 100이므로, 실제로는 단어의 길이와 상관없이 모든 쌍을 비교하는 것이 주요 성능 병목점입니다.
결론
두 클래스 모두 문제를 해결하는 방식은 유사하며, 주된 차이점은 BOJ_2179_비슷한단어_hash 클래스에서 해시맵을 사용하여 단어의 입력 순서를 저장한다는 점입니다. 그러나 현재 문제에서는 입력 순서를 고려한 비교가 추가적으로 구현되지 않았으므로, 두 클래스의 로직 처리 속도는 크게 다르지 않습니다.
입력 순서를 고려한 비교가 필요하다면, BOJ_2179_비슷한단어_hash 클래스에서 입력 순서를 비교하여 갱신하는 로직을 추가해야 합니다. 이를 통해 입력 순서를 정확히 고려한 최적의 결과를 얻을 수 있습니다.
'Algorithm > 코딩테스트' 카테고리의 다른 글
| [프로그래머스][JAVA] 이중 우선순위 큐 (0) | 2024.05.26 |
|---|---|
| [프로그래머스][JAVA] 디스크 컨트롤러 (0) | 2024.05.26 |
| [프로그래머스][JAVA] 주식 가격 (0) | 2024.05.23 |
| [프로그래머스][JAVA] 다리를 지나는 트럭 (0) | 2024.05.23 |
| [프로그래머스][JAVA] 베스트앨범 (0) | 2024.05.22 |