백준

[2607] 비슷한 단어 (JAVA)

댈팽이 2024. 6. 13. 01:40
728x90

# 문제 설명

영문 알파벳 대문자로 이루어진 두 단어가 다음의 두 가지 조건을 만족하면 같은 구성을 갖는다고 말한다.

  1. 두 개의 단어가 같은 종류의 문자로 이루어져 있다.
  2. 같은 문자는 같은 개수 만큼 있다.

예를 들어 "DOG"와 "GOD"은 둘 다 'D', 'G', 'O' 세 종류의 문자로 이루어져 있으며 양쪽 모두 'D', 'G', 'O' 가 하나씩 있으므로 이 둘은 같은 구성을 갖는다. 하지만 "GOD"과 "GOOD"의 경우 "GOD"에는 'O'가 하나, "GOOD"에는 'O'가 두 개 있으므로 이 둘은 다른 구성을 갖는다.

두 단어가 같은 구성을 갖는 경우, 또는 한 단어에서 한 문자를 더하거나, 빼거나, 하나의 문자를 다른 문자로 바꾸어 나머지 한 단어와 같은 구성을 갖게 되는 경우에 이들 두 단어를 서로 비슷한 단어라고 한다.

예를 들어 "DOG"와 "GOD"은 같은 구성을 가지므로 이 둘은 비슷한 단어이다. 또한 "GOD"에서 'O'를 하나 추가하면 "GOOD" 과 같은 구성을 갖게 되므로 이 둘 또한 비슷한 단어이다. 하지만 "DOG"에서 하나의 문자를 더하거나, 빼거나, 바꾸어도 "DOLL"과 같은 구성이 되지는 않으므로 "DOG"과 "DOLL"은 비슷한 단어가 아니다.

입력으로 여러 개의 서로 다른 단어가 주어질 때, 첫 번째 단어와 비슷한 단어가 모두 몇 개인지 찾아 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 단어의 개수가 주어지고 둘째 줄부터는 한 줄에 하나씩 단어가 주어진다. 모든 단어는 영문 알파벳 대문자로 이루어져 있다. 단어의 개수는 100개 이하이며, 각 단어의 길이는 10 이하이다.

출력

입력으로 주어진 첫 번째 단어와 비슷한 단어가 몇 개인지 첫째 줄에 출력한다.

 

# 정답 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine()); //단어의 개수
        String word = br.readLine(); //첫 번째 단어

        HashMap<Character, Integer> list = new HashMap<>(); //첫 번째 단어의 알파벳, 개수
        for (int i = 0; i < word.length(); i++) {
            list.put(word.charAt(i), list.getOrDefault(word.charAt(i), 0) + 1);
        }

        int answer = 0; //비슷한 단어 개수

        //비슷한 단어인지 검사
        for (int n = 0; n < N-1; n++) {
            String targetWord = br.readLine();
            HashMap<Character, Integer> hashMap = new HashMap<>(list);
            boolean isCorrect = true; //같은 구성인지 판별
            int different = 0; //종류나 수가 다른 알파벳 수
            int wordSum = word.length(); //알파벳 수

            //알파벳의 종류와 수가 같으면 같은 구성
            for (int i = 0; i < targetWord.length(); i++) {
                //알파벳 종류가 같은 경우
                if (hashMap.containsKey(targetWord.charAt(i))) {
                    if (hashMap.get(targetWord.charAt(i)) > 0) {
                        hashMap.put(targetWord.charAt(i), hashMap.get(targetWord.charAt(i)) - 1);
                        wordSum--;
                    }
                    //알파벳 수가 다른 경우
                    else {
                        isCorrect = false;
                        different++;
                    }
                }
                //알파벳 종류가 다른 경우
                else {
                    isCorrect = false;
                    different++;
                }
            }

            //알파벳 개수의 차가 1보다 크면 안됨
            if (wordSum <= 1) {
                //같은 구성이면 비슷한 단어임
                if (isCorrect) {
                    answer++;
                }
                //다른 구성이어도 different가 1이면 비슷한 단어임
                else {
                    if (different == 1) {
                        answer++;
                    }
                }
            }
        }

        bw.write(String.valueOf(answer));
        bw.flush();
    }
}

 

첫 번째 단어의 알파벳과 알파벳의 개수를 hashMap에 저장한다.

 

현재 단어가 같은 구성인지 확인한다.

알파벳 종류와 개수가 같으면 같은 구성이다.

 

다른 구성이어도 비슷한 단어가 될 수 있다.

한 문자를 더하거나, 빼거나, 다른 문자로 바꿨을 때 같은 구성이 되면 비슷한 단어이다.

이를 판별하기 위해 different에 종류가 다른 알파벳 수를 저장하고, wordSum을 이용하여 알파벳 개수의 차를 저장한다.

 

비슷한 단어이면 answer를 1 증가한다.

  • 같은 구성인 단어 중, 알파벳 개수가 1 이하인 단어
  • 다른 구성인 단어 중, 알파벳 개수가 1 이하이고 different가 1인 단어

728x90