[JAVA] BOJ(백준) - 비슷한 단어 - 2607

문제내용

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

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

출력

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

---

문제풀이

첫번째 단어와 비교될 단어의 길이에 따라 조건을 분기해서 로직을 짜주는 방식이다.

여기서 첫번째 단어는 oriStr, 비교될 단어(그외 단어)는 compStr이라 하겠다.

 

1. 문제에서 나와있다시피 첫번째 단어와 그외의 단어를 비교하는 것이기 때문에 첫번째 단어에 어떤 알파벳들이 얼마나 들어가 있는지 저장해놓을 공간이 필요하고, 필자는 HashMap에 key: 알파벳 , value: 개수 로해서 저장해놨다.

 

2. compStr의 알파벳을 하나씩 탐색하면서 알파벳이 HashMap에 key값으로 있고, value값이 0보다 클때 ,

알파벳이 몇개나 같은지 알려줄 cnt변수를 +1 해주고,

key값에 해당하는 value를 -1 해준다.

이 작업은 compStr의 알파벳이 oriStr의 알파벳과 얼마나 일치하는지를 나타내주기 위한 작업이다.

 

3. oriStr과 compStr의 길이에 따라 조건을 분기해준다.(길이 차이는 최대 1로 해준다)

oriStr.length()가 더 긴 경우 -> compStr의 모든 알파벳은 oriStr에 포함돼야 비슷한단어로 만들수 있음.

oriStr.length()가 더 짧은 경우 -> oriStr의 모든 알파벳은 compStr에 포함돼야 비슷한단어로 만들수 있음.

길이가 같은 경우 -> oirStr의 모든 알파벳이 compStr에 포함되거나 compStr 알파벳과 다른 알파벳은 하나여야함.

 

위의 과정으로 문제를 풀수 있는데 이게 생각보다 헷갈릴수 있는부분이라고 생각한다.

제일 좋은건 코드를보고 스스로 생각해보는것..

 

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

/**
 * 1. 첫번째 단어에 있는 알파벳들이 각각 몇번 나오는지 세기.
 * 2. 단어 길이차이에 따라 분기문으로 나눠서 체크하기(최대 1차이)
 * 3. 비교될 단어길이가 더 길면 -> 1번 가지고 비교될 단어의 알파벳들과 비교해서 알파벳 종류별 개수를 셈 -> 총개수가 비교될단어의 길이와 같아야함.
 * 4. 비교될 단어길이가 더 짧음 -> 1번 가지고 비교될 단어의 알파벳들과 비교해서 알파벳 종류별 개수를 셈 -> 총개수가 언래단어의 길이와 같아야함.
 * 5. 길이가 같으면 -> 1번 가지고 비교될 단어의 알파벳들과 비교해서 알파벳 종류별 개수를 셈 -> 총개수가 비교될단어의 길이와 같거나 -1 작아야함.
 * @author USER
 *
 */
public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		String[] arr = new String[n];
		
		for(int i=0; i<n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			arr[i] = st.nextToken();
		}
		
		//첫번째 단어 알파벳 개수 세고 HashMap에 넣기.
		HashMap<Character, Integer> alpha = new HashMap<>();
		for(int i=0; i<arr[0].length(); i++)
			alpha.put(arr[0].charAt(i), alpha.getOrDefault(arr[0].charAt(i), 0)+1);
			
		int ans = 0;
		for(int i=1; i<arr.length; i++) {//모든단어 탐색
			String oriStr = arr[0]; //첫번째 단어
			String compStr = arr[i]; //비교될 단어
			//위에서 저장해놓은 첫번째 단어의 알파벳들
			HashMap<Character, Integer> tempAlpha = new HashMap<Character, Integer>(alpha);
			
			int cnt = 0;//알파벳 개수 세기.
			for(int j=0; j<compStr.length(); j++) {//비교될 단어의 알파벳 하나씩 탐색
				char key = compStr.charAt(j);
				//HashMap에 비교될 단어 알파벳 존재하고 남은개수가 1개 이상일때만 체크
				if(tempAlpha.containsKey(key) && tempAlpha.get(key)>0) {
					tempAlpha.put(key, tempAlpha.get(key)-1);//탐색한 알파벳 개수 하나 줄이기
					cnt++;//첫번째 단어와 알파벳이 같을때니깐 개수 증가.
				}
			}
			
			if(compStr.length() == oriStr.length()-1) {//비교될 단어가 1글자 더 짧다.
				if(cnt == compStr.length()) ans++; //비교될 단어의 모든 알파벳이 기존 단어에 포함돼야 ans 증가.
			}
			else if(compStr.length() == oriStr.length()+1) {//비교될 단어가 1글자 더 길다.
				if(cnt == oriStr.length()) ans++; //기존단어의 모든 알파벳이 비교될 단어에 포함돼야 ans 증가.
			}
			else if(compStr.length() == oriStr.length()) {//길이같음.
				//알파벳이 같거나 비교될 단어의 알파벳이 하나 다를 경우만 ans 증가.
				if(cnt == compStr.length() || cnt == compStr.length()-1) ans++;
			}
		}//for
		System.out.println(ans);
	}
}

---

마치며

처음에 실버3 문제로 얕보고 접근했는데 그냥 구현해버리기엔 생각보다 예외상이 좀 있었고, 알파벳이 얼마나 포함되는지를 알려주는 로직에서 약간 헷갈렸었을때를 제외하고는 무난한 문제라고 생각한다.