! [Java][백준] #6518 - 오타 자동 수정

🔗 백준 6518 - 오타 자동 수정

문제

알고리즘 분류

• 자료 구조
• 브루트포스 알고리즘
• 많은 조건 분기
• 해시를 사용한 집합과 맵

---

풀이

1. 입력

• ArrayList에 사전 단어 저장
• 수정할 단어의 갯수 q를 입력받아 q번에 걸쳐 단어 입력

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        List<String> dictionary = new ArrayList<>();
        for(int i = 0; i<n; i++){
            dictionary.add(br.readLine());
        }
        int q = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i<q; i++){
            String word = br.readLine();
            ...
        }

2. 단어가 사전에 있는지 확인

• list의 contains함수를 이용해 사전에 포함된 단어인지 확인

            // 단어가 사전에 있으면 correct
            if (dictionary.contains(word)){
                sb.append(word).append(" is correct\n");
            }

3. 비슷한 단어인지 확인

• 비슷한 단어인지 확인해 t/f값을 반환하는 함수를 만들어 호출함

			else { // 아니면 비슷한 지 확인
                // 사전을 돌면서
                boolean isSimilar = false;
                for (String dict_word : dictionary){
                    isSimilar = similarCheck(word, dict_word);
                    ...
                }

            }

3.1. 단어의 길이가 같은 경우

• 두 단어 간 다른 문자의 수를 확인

        if (word_len == dword_len){
            int count = 0;
            for(int i = 0; i<word_len; i++){
                if (word.charAt(i) != dict_word.charAt(i)){
                    count++;
                }
            }
            ...
        }

3.1.1. 글자 한 개를 잘못 적은 경우

• 즉, 다른 문자가 1개인 경우
• ex) letter를 ketter로 쓴 경우

            if(count<2){ // 하나를 잘못 적은 경우
                return true;
            }

3.1.2. 글자 두 개를 잘못 적은 경우

• 즉, 다른 문자가 2개인 경우
• ex) letter를 lettre로 쓴 경우
  - 틀린 두 글자의 순서를 바꿨을 때 같은 단어인지 확인

			else if(count == 2){ // 두개가 다른 경우 (인접한)순서를 바꾸면 같은 지 확인
                for(int i = 0; i<word_len-1; i++){
                    if (word.charAt(i) != dict_word.charAt(i)){
                  		// 순서 바꿔보기
                        if(word.charAt(i) == dict_word.charAt(i+1) &&
                                word.charAt(i+1) == dict_word.charAt(i)){
                            return true;
                        }
                    }
                }
            }

3.2 단어의 길이가 다른 경우

3.2.1 수정할 단어의 길이가 1개 더 많은 경우

• ex) letter를 lettter로 쓴 경우,
• ex) will을 willl로 쓴 경우,
• 맨 앞이나 맨 뒤에 한 글자를 더 썼다면 contains함수로 확인 가능
• 아니라면 substring함수를 통해 해당 글자만 제외한 뒤 비교
  

		else if(word_len == dword_len + 1){
            if (word.contains(dict_word))
                return true;
            for(int i = 0; i<dword_len; i++){
            //그 글자를 빼면 같아지는지 검증
                if(word.charAt(i) != dict_word.charAt(i)){
                    if((word.substring(0, i) + word.substring(i + 2))
                            .equals(dict_word)){
                        return true;
                    }
                }
            }
        }

3.2.2. 수정할 단어의 길이가 1개 더 적은 경우

• ex) letter를 leter로 쓴 경우,
• ex) dictionary를 dictonary로 쓴 경우,
• 맨 앞이나 맨 뒤에 한 글자를 더 썼다면 contains함수로 확인 가능
• 아니라면 substring함수를 통해 해당 글자만 제외한 뒤 비교

        // 하나를 적게 썼을 때
        else if(word_len + 1 == dword_len){
            if (dict_word.contains(word))
                return true;
            for(int i = 0; i<word_len; i++){
                //사전단어에서 그 위치의 글자를 빼면 같아지는지 검증
                if(word.charAt(i) != dict_word.charAt(i)){
                    if((dict_word.substring(0, i) + dict_word.substring(i + 1))
                            .equals(word)){
                        return true;
                    }
                }
            }
        }

3.3 그 외의 경우

• 위 경우 모두 해당하지 않는다면 비슷하지 않은 것

        return false;

4. 비슷한 지 확인한 결과(t/f)값에 따라 결과 출력

// 메인 함수에 있는 코드

                    if (isSimilar){
                        sb.append(word).append(" is misspelling of " + dict_word + "\n");
                        break;
                    }
                }
                if(!isSimilar) sb.append(word).append(" is unknown\n");
            }
        }
        System.out.println(sb);

전체 코드

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

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

        List<String> dictionary = new ArrayList<>();
        for(int i = 0; i<n; i++){
            dictionary.add(br.readLine());
        }
        int q = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i<q; i++){
            String word = br.readLine();
            // 단어가 사전에 있으면 correct
            if (dictionary.contains(word)){
                sb.append(word).append(" is correct\n");
            } else { // 아니면 비슷한 지 확인
                // 사전을 돌면서
                boolean isSimilar = false;
                for (String dict_word : dictionary){
                    isSimilar = similarCheck(word, dict_word);
                    if (isSimilar){
                        sb.append(word).append(" is misspelling of " + dict_word + "\n");
                        break;
                    }
                }
                if(!isSimilar) sb.append(word).append(" is unknown\n");
            }
        }
        System.out.println(sb);
    }
    public static boolean similarCheck(String word, String dict_word){
        int word_len = word.length();
        int dword_len = dict_word.length();
        if (Math.abs(word_len - dword_len) > 2 )
            return false;
        if (word_len == dword_len){
            int count = 0;
            for(int i = 0; i<word_len; i++){
                if (word.charAt(i) != dict_word.charAt(i)){
                    count++;
                }
            }
            if(count<2){ // 하나를 잘못 적은 경우
                return true;
            }else if(count == 2){ // 두개가 다른 경우 (인접한)순서를 바꾸면 같은 지 확인
                for(int i = 0; i<word_len-1; i++){
                    if (word.charAt(i) != dict_word.charAt(i)){
                        if(word.charAt(i) == dict_word.charAt(i+1) &&
                                word.charAt(i+1) == dict_word.charAt(i)){
                            return true;
                        }
                    }
                }
            }
        } //하나를 많이 썼을 때
        else if(word_len == dword_len + 1){
            if (word.contains(dict_word))
                return true;
            for(int i = 0; i<dword_len; i++){
            //그 글자를 빼면 같아지는지 검증
                if(word.charAt(i) != dict_word.charAt(i)){
                    if((word.substring(0, i) + word.substring(i + 2))
                            .equals(dict_word)){
                        return true;
                    }
                }
            }
        }
        // 하나를 적게 썼을 때
        else if(word_len + 1 == dword_len){
            if (dict_word.contains(word))
                return true;
            for(int i = 0; i<word_len; i++){
                //사전단어에서 그 위치의 글자를 빼면 같아지는지 검증
                if(word.charAt(i) != dict_word.charAt(i)){
                    if((dict_word.substring(0, i) + dict_word.substring(i + 1))
                            .equals(word)){
                        return true;
                    }
                }
            }
        }
        return false;
    }
}

정말 날 화나게 한 문제
언젠가 풀 수 있겠지?