Baekjoon 2607 비슷한 단어 JAVA

2607번: 비슷한 단어

문제

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

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 이하이다.

출력

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

풀이

입력되는 숫자는 총 입력될 문자열의 개수이다.

첫 번째 줄의 문자열은 기준점이 되는 문자열이다.

나머지 입력되는 문자열들은 첫 번째로 입력된 문자열을 만들 수 있는 문자열인지 비교될 문자열이다.

 

먼저 첫 번째 문자열을 이루는 각 알파벳들을 구분하여 알파벳별로 카운팅을 해준다. (arr에 저장)

 

이후로 입력되는 문자열들 또한 각 알파벳 개수를 카운팅해준다. (brr에 저장)

카운팅 된 문자열들을 기준이 되는 첫 번째 문자의 수들과 비교하면서 arr[i]-brr[i] 연산을 해준다.

ex) string A = "ABBB", string B = "BBBCC"

이때 arr에서는 A가 존재하지만 brr에는 A가 존재하지 않기에 1 을 반환하며

arr에는 C가 존재하지 않지만 brr에는 C가 존재하기에 -2을 반환하게 될 것이다.

이 두 값을 더하면 -1로 나오며 문제에서 제시하는 조건을 만족하지 않기에

절대값 함수인 Math.abs를 사용하여 절대적으로 다른 값을 더해준다.

 

if 조건문에 대해서는 "하나의 문자를 다른 문자로 바꾸어 나머지 한 단어와 같은 구성을 갖게 되는 경우"이다.

입력되는 문자열의 길이가 비교하는 길이의 문자열과 같다면 한 글자를 다른 글자로 바꿀 수 있다면

비슷한 단어라고 생각하기에 diff 문자 개수를 2이하 일경우에 증가시킨다.

ex) ABBB, BBBC

위의 값은 길이가 동일할때 A로 인한 1, C로 인한 1이 생기며 다른 문자의 개수는 2개이지만 BBBC를 ABBB로 바꿀 수 있기에

비슷한 문자로 카운팅한다.

 

두 번째 else if는 "한 단어에서 한 문자를 더하거나, 빼거나"에 대한 조건이다.

두 문자열의 길이를 계산하여 길이차이가 1이며, 다른 문자의 개수가 1이라면 하나를 빼거나 더하는 상황이다.

 

코드

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()), cnt=0;
		String ori = br.readLine();
		int [] arr = new int [26];
		for(int i=0;i<ori.length();i++)
			arr[ori.charAt(i)-'A']++;
		for(int i=1;i<n;i++) {
			String temp = br.readLine();
			int [] brr = new int[26];
			for(int j=0;j<temp.length();j++)
				brr[temp.charAt(j)-'A']++;
			int tmp=0;
			for(int j=0;j<26;j++)
				tmp+=Math.abs(arr[j]-brr[j]);
			if(temp.length()==ori.length() && tmp<=2)
				cnt++;
			else if(Math.abs(temp.length()-ori.length())==1 && tmp==1 )
				cnt++;
		}
		System.out.println(cnt);
	}
}