[백준] 2607: 비슷한 단어 - JAVA

in Algorithm on 구현

https://www.acmicpc.net/problem/2607

풀이

단어가 주어지고, 다음에 주어지는 단어들이 첫번째 단어와 비슷한 단어인지 체크하는 문제이다.

비슷한 단어란 다음과 같이 판별한다.

  1. 길이가 같을 경우, 알파벳의 구성이 같다.

  2. 길이가 다를 경우 알파벳 하나를 더하거나 빼서 같은 구성으로 만들 수 있다.

첫 번째 단어를 길이 26의 int배열로 받아 비교해주었다.

비교할 단어를 위의 int배열과 비교하여 구성이 같은지 판단하여 cnt라는 개수로 체크한다.

두 단어의 길이가 같을 경우 cnt가 첫 단어의 길이와 같거나 cnt가 첫 단어의 길이보다 1 작다면 만족한다.

비교하는 단어가 1만큼 작을 경우, 첫 단어에 존재하는 알파벳과 다른 알파벳을 가지고 있으면 안된다. 즉, cnt가 비교하는 단어의 길이와 같을 때 만족한다.

비교하는 단어가 1만큼 클 경우, 값을 하나 빼도 첫 단어의 구성과 같아야 한다. cnt가 첫 단어의 길이와 같다면 만족한다.

메모리: 14076KB

시간: 120ms

언어: Java 11

코드

import java.io.*;

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

        int ans = 0;
        for (int i = 0; i < N - 1; i++) {
            String tmp = br.readLine();
            ans += check(word, tmp);
        }

        System.out.println(ans);
    }

    private static int check(String a, String b) {
        if (Math.abs(a.length() - b.length()) > 1) {
            return 0;
        }

        int[] alpha = new int[26];
        for (int i = 0; i < a.length(); i++) {
            alpha[a.charAt(i) - 'A']++;
        }

        int cnt = 0;
        for (int i = 0; i < b.length(); i++) {
            if (alpha[b.charAt(i) - 'A'] > 0) {
                cnt++;
                alpha[b.charAt(i) - 'A']--;
            }
        }

        if (a.length() == b.length() && (a.length() == cnt || a.length() - 1 == cnt)) {
            return 1;
        }

        if (a.length() + 1 == b.length() && a.length() == cnt) {
            return 1;
        }

        if (a.length() - 1 == b.length() && b.length() == cnt) {
            return 1;
        }

        return 0;
    }

}