[백준_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"은 비슷한 단어가 아니다.

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

 

[코드]

import java.util.*;

public class BaekJoon_2607 {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		
		int n=sc.nextInt();
		String str=sc.next();
		int[] alpabet=new int[26];
		
		for(int i=0;i<str.length();i++)
			alpabet[str.charAt(i)-'A']++;
		
		int result=0;
		for(int t=0;t<n-1;t++) {
			String compar=sc.next(); // 비교할 문자열
			int[] temp=alpabet.clone();
			
			int count=0; // 기준 문자열과 비교할 문자열에 공통으로 포함된 알파벳의 개수
			for(int i=0;i<compar.length();i++) {
				if(temp[compar.charAt(i)-'A']>0) { // 기준 문자열에 포함된 알바벳인 경우
					count++;
					temp[compar.charAt(i)-'A']--;
				}
			}
			
			// 1. 기준 문자열이 비교 문자열 보다 한 글자가 긴 경우
			if(str.length()-1==compar.length()&&count==compar.length())
				result++;
			// 2. 두 문자열의 길이가 같은 경우
			else if(str.length()==compar.length()) {
				if(count==str.length()||count==str.length()-1)
					result++;
			}
			// 3. 기준 문자열이 비교 문자열 보다 한 글자가 긴 경우 
			else if(str.length()+1==compar.length()) {
				if(count==str.length())
					result++;
			}
		}
				
		System.out.println(result);
	}

}

 

[고찰]

 이번 문제는 경우의 수를 잘 나눠야 하는 문제였다. 두 문자열이 비슷할 수 있는 경우는 세가지로 나뉘는데 아래와 같다.

 

1. 기준 문자열의 길이 -1 == 비교 문자열 길이

2. 기준 문자열의 길이 == 비교 문자열 길이

3. 기준 문자열의 길이 == 비교 문자열 길이-1

 

즉, 이 문제의 핵심 포인트는 두 문자열이 비슷한 문자열이 되기 위해서는 길이가 같거나 문자 하나만 많아야 한다는 것이다. 이를 잘 고려하여 위의 경우를 모두 조건화해주면 정답 처리를 받을 수 있는 문제였다.