#2607 : 비슷한 단어

풀이방법

2022.03.02

기준이 되는 문자열의 알파벳별 개수를 센다.

길이가 26인 정수 배열 arr1을 선언하여,

arr1[0]에는 A의 개수를, arr1[1]에는 B의 개수를... arr1[25]에는 Z의 개수를 저장하는 방식으로 세면 된다.

 

그 다음 문자열부터 다음의 과정을 거친다.

1. 기준문자열의 알파벳별 개수를 셌던 것과 같은 방식으로, 문자열의 알파벳별 개수를 세어 arr2에 저장한다.

2. int[] gap을 선언한다. gap[i] = arr1[i] - arr2[i]이다.

3. gap[0]~gap[25]를 점검한다.

   2 이상의 정수 혹은 -2 이하의 정수가 저장된 요소가 존재하면 즉시 점검을 종료하고 다음 문자열로 넘어간다.

   2개 이상의 문자를 변경해야 할 경우, 이 문자열은 비슷한 문자열이 아니기 때문이다.

   1이 저장된 요소가 있다면 해당 알파벳이 기준 문자열보다 하나 모자라다는 의미이다. less 변수를 1 증가시킨다.

   -1이 저장된 요소가 있다면 해당 알파벳이 기준 문자열보다 하나 많다는 의미이다. more 변수를 1 증가시킨다.

4. 밑줄 친 상황에 해당하는 요소가 하나도 없어 점검이 정상적으로 끝났을 경우,

   다음의 기준에 따라 비슷한 문자열인지를 판단한다.

• more >1 인 경우 : 2가지 이상의 글자를 지워줘야 성분이 같아지므로, 비슷한 단어가 아님.
• less > 1 인 경우 : 2가지 이상의 글자를 추가해줘야 성분이 같아지므로, 비슷한 단어가 아님.
• more과 less가 모두 0인 경우 : 성분이 같은 단어임.
• more == 0 && less == 1 : 글자를 하나만 추가해주면 성분이 같아지므로, 비슷한 단어임.
• more == 1 && less == 0 : 글자를 하나만 지워주면 성분이 같아지므로, 비슷한 단어임.
• more == 1 && less == 1 : 한 글자를 다른 글자로 바꾸어주면 성분이 같아지므로, 비슷한 단어임.

코드

Java(2022.03.02)

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

public class Main {
	
	static int n;	//단어 수
	static int[] first;	//첫 번째 단어의 알파벳 구성
	static int[] rest;	//나머지 단어의 알파벳 구성
	static int[] gap;	//두 단어의 알파벳별 개수차이
	static int more, less;	//기준 단어보다 한 개 많은 & 적은 알파벳의 가짓수
	static boolean v;	//비슷한 문자열이면 true
	static int ans;	//정답

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		
		//첫 번째 문자열 읽어와 알파벳 구성을 저장
		char[] input = br.readLine().toCharArray();
		first = new int[26];
		for(char c : input) {
			first[c-'A']++;
		}
		
		//나머지 n-1개의 문자열
		ans = 0;
		for(int i = 0; i<n-1; i++) {
			//문자열 읽어와서 알파벳 구성을 저장
			char[] temp = br.readLine().toCharArray();
			rest = new int[26];
			for(char c: temp) {
				rest[c-'A']++;
			}
			
			//두 문자열의 알파벳별 개수차이
			gap = new int[26];
			for(int j = 0; j<26; j++) {
				gap[j] = first[j] - rest[j];
			}
			
			//두 문자열이 비슷한지 판단
			more = 0;
			less = 0;
			v = true;
			for(int j : gap) {
				if(j>1 || j<-1) v = false;
				if(j == -1) more++;
				if(j == 1) less++;
			}
			
			if(v) {
				if(more > 1) v = false;
				if(less > 1) v = false;
			}
			
			if(v) ans++;
			
		}
		
		//정답 출력
		System.out.print(ans);
		

	}

}

 

Java(2022.03.15, E-PPER 제출을 위한 solution 함수 형식)

	public static int solution(int n, String [] words) {
		int answer=0;

		char[] input = words[0].toCharArray();
		int[] first = new int[26];
		for(char c : input) {
			first[c-'A']++;
		}
		
		for(int i = 1; i<n; i++) {
			//문자열 읽어와서 알파벳 구성을 저장
			char[] temp = words[i].toCharArray();
			int[] rest = new int[26];
			for(char c: temp) {
				rest[c-'A']++;
			}
			
			//두 문자열의 알파벳별 개수차이
			int[] gap = new int[26];
			for(int j = 0; j<26; j++) {
				gap[j] = first[j] - rest[j];
			}
			
			//두 문자열이 비슷한지 판단
			int more = 0;
			int less = 0;
			boolean v = true;
			for(int j : gap) {
				if(j>1 || j<-1) v = false;
				if(j == -1) more++;
				if(j == 1) less++;
			}
			
			if(v) {
				if(more > 1) v = false;
				if(less > 1) v = false;
			}
			
			if(v) answer++;
			
		}
		return answer;
	}