2607 - 비슷한 단어 (Java)

 

---

 

문제

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

 

 

풀이

총 3개의 경우로 나눠서 생각하면 편하다.

 

 

[들어오는 값이 기준값보다 짧은 경우]

• 짧은 경우에는 문자를 새롭게 하나 더해주는 경우의 수 밖에 없기 때문에 길이 차이는 1만 나야한다.
• 기준값이 ABC 일 때, AB 와 같이 새로 추가할 문자열 "C" 를 제외했을 때, 문자열의 구성이 모두 같아야 한다.

 

[들어오는 값이 기준값보다 긴 경우]

• 긴 경우에는 문자를 하나 저게하는 경우의 수 밖에 없기 때문에 길이 차이는 1만 나야한다.
• 기준값이 ABC 일 때,  ABDC 와 같이 제거할 문자열 "D" 를 제외했을 때, 문자열의 구성이 모두 같아야 한다.

[들어오는 값이 기준값과 길이가 같은 경우]

• 완전 구성이 똑같은 경우
• 한 알파벳만 다른 경우
  • 한 알파벳만 다르다는건, 매칭 되는 알파벳의 개수가 문자열의 길이 - 1 을 의미한다.
  • 예로 기준값이 ADA 일 때 ,DAD 를 보자. 
    
    • ADA 와 DAD 의 요소를 살펴보았을 때 각각 문자열에서 A 알파벳 한 개, D 알파벳 한 개를 뽑아 갈 수 있다. 그러면 매칭되는 알파벳이 2개이다. 문자열의 길이인 3보다 1 짧은 길이이고, 나머지 한 알파벳은 변경하면 끝이다.

난 해쉬로 구현했고 각 알파벳의 개수를 체킹해서 저장했고 

 

문자열 비교시 몇개가 매칭되는지에 저장하고 길이에 따라 분기하여 정답을 도출했다.

 

코드

import java.util.*;
import java.io.*;

public class Main {

    public void solution() throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Integer answer = 0;
        int n = Integer.parseInt(br.readLine());

        Map<String, Integer> mainMap = new HashMap<>();
        String[] mainArray = br.readLine().split("");

        for (int i = 0; i < mainArray.length; i++) {
            String token = mainArray[i];
            mainMap.put(token, mainMap.getOrDefault(token, 0) + 1);
        }


        for (int i = 0; i < n-1; i++) {
            String[] targetArray = br.readLine().split("");

            int mainLen = mainArray.length;
            int targetLen = targetArray.length;
            Map<String, Integer> targetMap = new HashMap<>();


            for (int j = 0; j < targetArray.length; j++) {
                String token = targetArray[j];
                targetMap.put(token, targetMap.getOrDefault(token, 0) + 1);
            }

            int count = 0;
            for (Map.Entry<String, Integer> stringIntegerEntry : targetMap.entrySet()) {
                String key = stringIntegerEntry.getKey();
                Integer num = stringIntegerEntry.getValue();

                // 일치하는 수를 카운트 해야한다.
                if(mainMap.containsKey(key)){

                    if (num != mainMap.get(key)) {
                        if(num > mainMap.get(key)) count += mainMap.get(key);
                        if(num < mainMap.get(key)) count += num;
                    }

                    if(num == mainMap.get(key)) count += num;
                }
            }

            // 짧은 경우에는 모든 값이 들어맞아야 한다.
            if(mainLen == targetLen + 1 && count == targetLen) answer++;

            // 긴 경우에는 하나만 달라야 한다.
            if(mainLen + 1 == targetLen && count == targetLen - 1) answer++;

            // 같은 경우에는 하나를 빼거나, 같은 경우를 포함한다.
            if(mainLen == targetLen && (count == targetLen - 1 || count == targetLen)) answer++;

        }

        System.out.println(answer);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

}

 

후기

 

해쉬로 풀었는데 대부분 배열로 풀었더라,,