[백준] 2607 비슷한 단어 - 구현(Implementation) + 문자열(String) JAVA

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

2607번: 비슷한 단어

코드설명

구현과 문자열에 관련한 문제입니다.

 

첫번째 단어 알파벳의 개수를 가지고 있는 alphabet[26]을 생성해주고, 비교단어들을 alphabet[26]과 비교해가면서 진행합니다.

 

문제의 기본 로직입니다.

1. 첫번째 단어의 알파벳 개수를 alphabet[26]에 아스키코드값을 활용하여 각 알파벳의 개수를 배열에 넣습니다.

2. 이후의 단어들을 기준 알파벳의 개수가 > 0 이라면, 해당 알파벳의 값을 -1 해주고, 제거한 알파벳의 개수를 calculated 에 +1 씩 증가시켜줍니다.

3. 만약에 기준단어와 비교 단어의 길이가 같다면, 비슷한 단어가 되기 위해서는 완전히 같은 단어이거나, 1가지 다른 경우여야합니다. 

해당 조건으로, 아래의 코드를 사용합니다.

if(arr[0].length() == arr[i].length() && ( arr[0].length() == calculated || arr[0].length() - 1 == calculated) )

4. 만약에 기준단어가 비교단어길이보다 더 짧다면, 비슷한 단어가 되기 위해서는 비교단어 길이가 1가지 뺴고는 모두 다 같은 알파벳으로 이루어져있어야합니다. 1가지의 알파벳은 비교단어가 더 많습니다.

if(arr[0].length() + 1 == arr[i].length() && arr[i].length()  = calculated + 1)

5. 만약에 기준단어가 비교단어길이보다 길다면, 비슷한 단어가 되기 위해서는 비교단어 길이는 기준단어에 완전히 포함되어야 합니다.

if(arr[0].length() - 1 == arr[i].length() && arr[i].length = calculated )

3 ~ 5 까지의 과정을 계속해서 반복합니다.

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
	
	public static int N, K;
	public static String[] arr;
	public static int answer = 0;
	
	public static int[] alphabet = new int[26];
	public static int[] compareAlphabet = new int[26];
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	arr = new String[N];
    	
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
        	arr[i] = st.nextToken();	
        	
        	if(i == 0) {
        		for(int j=0;j<arr[i].length();j++) { //첫번쨰 단어가 기준입니다.
        			alphabet[arr[i].charAt(j) - 'A'] += 1; //모든 단어가 대문자이기에 'A'(65)로 뻅니다.
        		}
        	}
    	}
    	
//    	두 단어의 길이가 같고, 한 문자를 다른 문자로 바꾸면 같은 구성이 되는 경우를 판별할 때 오류가 있는 경우입니다.
    	for(int i=1;i<N;i++) {
    		int calculated = 0;
    		int[] standardAlphabet = new int[26];
    		for(int j=0;j<26; j++) { //첫번쨰 단어가 기준입니다.
    			standardAlphabet[j] = alphabet[j]; //모든 단어가 대문자이기에 'A'(65)로 뻅니다.
    		}
    		
    		for(int j=0;j<arr[i].length();j++) {
    			if( standardAlphabet[arr[i].charAt(j) - 'A'] > 0 ) { //기준 단어 배열에서 알파벳을 찾아가면서 제거, 만약 해당 알파벳이 존재하지않는다면 제거안함
    				calculated += 1;
    				standardAlphabet[arr[i].charAt(j) - 'A'] -= 1; 
    			}
    		}
    		
    		//기준단어와 비교단어의 길이가 같고, 서로 다른 개수가 없거나, 한글자만 바뀐경우
    		if(arr[0].length() == arr[i].length() && (arr[0].length() == calculated || arr[0].length() - 1 == calculated)) {
    			answer += 1;
    		}
    		
    		//비교단어의 길이가 한개 긴 경우, calculated도 한개 적어야합니다.
    		else if(arr[0].length() + 1 == arr[i].length() && arr[i].length() - 1 == calculated) {
    			answer += 1;
    		}
    		
    		//비교 문자열이 짧은경우
    		else if(arr[0].length() == arr[i].length() + 1 && arr[i].length() == calculated) {
    			answer += 1;
    		}
    		
    		
    	}

    	System.out.println(answer);
    }

    
}

 

정답코드2입니다. HashMap을 활용한 코드입니다.

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, A, B, X, L, R, C, n, k, m, l, K, D, T;
	static int answer = 0;
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		String standard = br.readLine();
		HashMap<Character, Integer> hm = new HashMap<>();
		for(int i=0; i<standard.length(); i++) {
			hm.put(standard.charAt(i), hm.getOrDefault(standard.charAt(i), 0) + 1);
		}
		
		for(int i=0; i<N-1; i++) {
			HashMap<Character, Integer> hm2 = new HashMap<>(hm);
			String str = br.readLine();
			
			int sameCnt = 0;
			for(int j=0; j<str.length(); j++) {
				if(hm2.containsKey(str.charAt(j)) == true) {
					int value = hm2.get(str.charAt(j));
					if(value > 0) {
						sameCnt += 1;
						hm2.put(str.charAt(j), value - 1);
					}
				}
				
			}
			//만약 standard와 주어진 문자열의 길이가 같으면서
			//만약 sameCnt가 같다면, 즉 모든 단어가 일치한다면 비슷한단어이다.
			//만약 sameCnt가 다를때, 1개만 차이난다면 1개 차이이므로 비슷한 단어이다.
			if(standard.length() == str.length() && (standard.length() == sameCnt || standard.length() -1 == sameCnt)) {
				answer += 1;
			}
			//비교 단어의 길이가 한개 긴 경우, samecnt도 한개 적어야 합니다.
			else if(standard.length() +1 == str.length() && str.length() - 1 == sameCnt) {
				answer += 1;
			}
			//비교 문자열이 짧은경우
			//개수가 같아야만 합니다.
			else if(standard.length() == str.length() + 1 && str.length() == sameCnt) {
				answer += 1;
			}
			
		}
		System.out.println(answer);
		
	}

}