[백준 2607] 비슷한 단어(Java)

문제 링크 : https://www.acmicpc.net/problem/2607

이 문제는 문제의 조건을 차근차근 구현해나가면 됩니다. 이 문제의 핵심 풀이법은 비슷한 단어를 어떻게 구별하느냐입니다. 이는 다음의 3가지 방법으로 요약할 수 있습니다.

1. 기준값보다 길이가 1만큼 작을 경우
2. 기준값보다 길이가 1만큼 클 경우
3. 기준값과 길이가 같을 경우 (단어 치환 & 같은 문자열)

이를 계산하기 위해서는 현재값 중 기준값에 존재하는 알파벳 개수를 알야아 합니다. 1번 케이스의 경우 기준값보다 현재값이 길이가 작기 때문에 현재값이 기준값에 존재하는 알파벳과 다른 알파벳을 가지고 있으면 값을 추가 시 무조건 다른 구성으로 나타나기 때문에 만족하지 않습니다.

2번 케이스의 경우 기준값보다 현재값이 길이가 크기 때문에 값을 하나 빼도 기준값의 알파벳 구성과 같아야 합니다. 즉 현재값에서 기준값과 같은 알파벳의 개수가 기준값의 길이와 같다면 현재값에서 하나의 수를 빼도 같은 구성이기 때문에 조건을 만족합니다.

3번 케이스의 경우 2가지 케이스가 존재합니다. 먼저 현재값과 기준값이 동일한 구성을 가지고 있는 경우입니다. 이 경우는 항상 만족하며, 이는 현재값에서 기준값과 같은 알파벳의 개수와 기준값의 길이가 같다면 만족합니다. 두 번째 케이스는 단어를 치환하는 경우입니다. 이 경우는 현재값에서 기준값과 같은 알파벳의 개수가 기준값의 길이보다 1만큼 작다면 기준값과 다른 구성의 알파벳이 1개만 존재하는 경우이므로 치환하여 처리가 가능합니다.

다음은 코드입니다.

import java.util.*;
import java.io.*;

public class Main{
    static int N;
    static String standard;
    static int res = 0;
    static int[] alphabet = new int[26];
    static int[] check;

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

        // 기준값 알파벳 분석 : 알파벳 개수를 기록
        standard = br.readLine();
        for(int i=0;i<standard.length();i++){
            int idx = standard.charAt(i) - 'A';
            alphabet[idx]++;
        }

        // 나머지 값 분석
        for(int i=0;i<N-1;i++){
            check = alphabet.clone();
            String curr = br.readLine();

            // 길이 차이가 1 넘을 경우 같은 수가 될 수 없음
            if(Math.abs(curr.length() - standard.length())>1) continue;

            // cnt = 기준값과 같은 알파벳의 개수
            int cnt = 0;

            // 비교할 문자열의 알파벳 비교
            for(int j=0;j<curr.length();j++){
                int idx = curr.charAt(j) - 'A';

                // 만약 비교할 문자열의 알파벳이 기준 알파벳에도 존재할 때마다 값 증가
                // 이 때 중복 체크 방지하기 위해서 check 배열값 감소
                if(check[idx]>0){
                    cnt++;
                    check[idx]--;
                }
            }

            // 조건 비교
            // 1. 기준값보다 길이가 1만큼 작을 경우
            if(standard.length()-1 == curr.length()){
                // 현재값이 기준값에 존재하는 알파벳과 다른 알파벳을 가지고 있으면 안됨
                // 즉 현재값에서 기준값과 같은 알파벳의 개수(cnt)와 현재값의 길이(curr.length())가 같으면 만족
                if(cnt == curr.length()) res++;
            }

            // 2. 기준값보다 길이가 1만큼 클 경우
            else if(standard.length()+1 == curr.length()){
                // 값을 하나 빼도 기준값의 알파벳 구성과 같아야 함
                // 즉 현재값에서 기준값과 같은 알파벳의 개수(cnt)와 기준값의 길이(standard.length())가 같으면 만족
                if(cnt == standard.length()) res++;
            }

            // 3. 기준값과 길이가 같을 경우
            else if(standard.length() == curr.length()){
                // case 1. 현재값에서 기준값과 같은 알파벳의 개수(cnt)가 기준값의 길이(standard.length())가 같으면 만족
                if(cnt == standard.length()) res++;

                // case 2. 현재값에서 기준값과 같은 알파벳의 개수(cnt)가 기준값의 길이(standard.length())보다 1 작다면 만족
                else if(cnt == standard.length()-1) res++;
            }

        }

        System.out.println(res);
    }
}