백준 2607 비슷한 단어 Java

한국정보올림피아드 초등부 4번, 중등부 2번 문제인 비슷한 단어이다.

 

내 힘으로 풀긴 풀었지만 꽤 어려웠던 문제 같은데

이런 문제를 풀어내는 초등학생, 중학생이 있다니

더욱더 분발해야겠다.

 

N개의 단어가 주어지는데

첫 번째 단어와 N-1개의 단어들 중에

비슷한 단어의 개수를 출력하면 되는 문제이다.

 

비슷한 단어는 기준이 되는 문자나 주어진 문자 중

한 문자를 골라서 하나를 추가하거나 하나를 빼거나 하나의 문자를 다른 문자로 바꿨을 때

두 개의 단어가 같으면 비슷한 문자이다.

아예 단어 구성이 같은 단어도 카운트해줘야 한다.

 

처음엔 기준이 되는 문자열에서 만들 수 있는 모든 비슷한 단어를 구하는 방향으로

구현했는데 열심히 구현하고 틀렸다.

 

어떻게 구현할까 생각을 많이 했는데

초등부 문제라는 점을 감안해서

쉽게 구현하는 방법이 있을 거라고 생각했다. 

 

문제를 차근차근 살펴보니 해답은 간단했다.

비교할 문자열을 기준으로 비슷한 단어가 될 수 있는 경우는 세 가지이다.

 

1. 기준이 되는 문자열보다 길이가 한 글자 작은 경우

2. 기준이 되는 문자열보다 길이가 한 글자 큰 경우

3. 기준이 되는 문자열과 길이가 같은 경우

 

기준이 되는 문자열보다 길이가 한 글자 작은 경우엔

기준이 되는 문자열에서 한 글자를 빼버리면 되므로

비교할 문자열이 기준이 되는 문자열과 구성이 전부 일치하면 비슷한 단어이다.

 

기준이 되는 문자열보다 길이가 한 글자 큰 경우엔

비교할 문자열에서 한 글자 빼버리면 되므로

비교할 문자열의 구성이 기준이 되는 문자열의 길이만큼 일치하면 비슷한 단어이다.

 

기준이 되는 문자열과 길이가 같은 경우엔

아예 구성이 같은 경우, 비슷한 단어이고

기준이 되는 문자열에서 한 글자를 다른 문자를 바꿔버리면 되므로

두 단어의 구성이 길이-1 만큼만 일치해도 비슷한 단어이다.

 

기준이 되는 문자열의 구성을 charAt메소드를 이용해서 int배열에 저장해두고

비교할 문자열과 얼만큼 일치하는지 비교해서 문제를 풀었다.

 

실행 속도도 가장 빠르고 고민 끝에 해결한 문제라 뿌듯했다.

import java.io.*;
 
public class Q2607 {
 
    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine())-1;
        String standard = reader.readLine();
        int len = standard.length();
        int[] alphabet = new int[26]; 
        for(int i=0; i<len; i++) {
            alphabet[standard.charAt(i)-'A']++;
        }
        
        int ans = 0;
        while(n-- > 0) {
            int[] temp = alphabet.clone();
            String comp = reader.readLine();
            int cnt = 0;
            for(int i=0; i<comp.length(); i++) {
                if(temp[comp.charAt(i)-'A'] > 0) {
                    cnt++;
                    temp[comp.charAt(i)-'A']--;
                }
            }
            if(len-1 == comp.length() && cnt == comp.length()) { //길이가 한글자 작을 때
                ans++;
            } else if(len == comp.length()) { //길이가 같을 때
                if(cnt == len || cnt == len-1) ans++;
            } else if(len+1 == comp.length()) { //길이가 한글자 클 때
                if(cnt == len) ans++;
            }
        }
        System.out.println(ans);
    }
}