[TIL] 백준 비슷한 단어 실버2

오늘은 백준 비슷한 단어 실버2 문제를 풀어보았다.
혹시나 시간 초과가 날까 걱정이 들긴 했지만
구현 문제인 것 같다는 느낌이 들어 약간 안심하고 풀어보았다.

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

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

public class Main {
    private static int N, count = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(bufferedReader.readLine());
        String str = bufferedReader.readLine();
        HashMap <String, Integer> map = new HashMap<>();
        String arr[] = str.split("");

        //첫번째 단어
        for(int j=0;j<arr.length;j++) {
            map.put(arr[j], map.getOrDefault(arr[j] + 1, 1));
        }

        // 두 단어가 같은 구성을 갖는 경우
        // 한 단어에서 한 문자를 더하거나 빼서 같은 구성 = 하나만 다른거(길이 +-1)
        // 하나의 문자를 다른 문자로 바꾸어 같은 구성 = 하나만 글자 다른거
        for(int i=0;i<N-1;i++){
            str = bufferedReader.readLine();
            String s_arr[] = str.split("");
            compare(map, s_arr);
        }

        System.out.println(count);
    }

    private static void compare(HashMap<String, Integer> map, String s_arr[]){
        HashMap <String, Integer> smap = new HashMap<>(map); //main의 map은 변경안되게 새로 만듬
        int fail = 0;

        for(int i=0;i<s_arr.length;i++) {
            if(smap.containsKey(s_arr[i])){
                if(smap.get(s_arr[i]) >= 1)
                    smap.put(s_arr[i], smap.get(s_arr[i]) - 1);
                else{
                    //문자는 있는데 길이가 다른거
                    fail++;
                }
            } else{
                fail++;
            }
        }

        if(fail == 0 || (fail == 1 && (map.size() == s_arr.length - 1 || map.size() == s_arr.length + 1 || map.size() == s_arr.length)))
        {
            //비슷한 단어임
            count++;
        }
    }
}

반례

2
AAAAA
AAAAAA
결과 1
하지만 0이 나옴

잘못된 부분

1. map.put(arr[j], map.getOrDefault(arr[j] + 1, 1));
   map.getOrDefault에서 앞에는 키에 해당하는 값을 반환하는 것이므로 arr[j] + 1은 적합하지 않음.
   java map.put(arr[j], map.getOrDefault(arr[j], 0)+1);

2. fail == 1 && (smap.size() == s_arr.length - 1에서 smap.size()는 키 기준이므로 위의 반례에서는 size가 1이 나옴

그래도 틀림

반례

10
ABAAC
ABAA
ABAC
ABAB
ABAAA
ABCAA
ABSAC
AABBB
AA
ABC
답: 5
ABAA
ABAC
ABAAA
ABCAA
ABSAC

위의 반례에서 8이 나왔었다.

1. ABAB가 비슷한 문자로 나오길래 fail이 쓰이는 경우를 곰곰이 생각해봤다.
   문자는 있는데 더 초과되는 경우.
   즉 비슷한 문자일려면 문자 구성에서 하나를 빼야되는 경우를 말한다.
   그래서 fail이 1인 경우 mapSize = s_arr.length - 1인 경우만 가능하다.

2. AA에서 비슷한 문자로 나왔다.
   AA 자체는 둘다 포함되어 있기에 fail이 0이라고 비슷한 단어라 하면 안됐던 것이다.
   그래서 mapSize == s_arr.length를 넣어줬다.

3. fail이 1이고 mapSize가 2이상인 것
   다른 반례이지만 2 A B인 경우 B를 A로 교환해버리면 된다고 하면 안된다.
   따라서 fail이 1일 때 첫 단어는 2글자 이상이어야 한다.

정답 코드

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

public class Main {
    private static int N, count = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(bufferedReader.readLine());
        String str = bufferedReader.readLine();
        HashMap <String, Integer> map = new HashMap<>();
        String arr[] = str.split("");

        //첫번째 단어
        for(int j=0;j<arr.length;j++) {
            map.put(arr[j], map.getOrDefault(arr[j], 0)+1);
        }

        for(int i=0;i<N-1;i++){
            str = bufferedReader.readLine();
            String s_arr[] = str.split("");
            compare(map, s_arr, arr.length);
        }

        System.out.println(count);
    }

    private static void compare(HashMap<String, Integer> map, String s_arr[], int mapSize){
        HashMap <String, Integer> smap = new HashMap<>(map);
        int fail = 0;

        for(int i=0;i<s_arr.length;i++) {
            if(smap.containsKey(s_arr[i])){
                if(smap.get(s_arr[i]) >= 1)
                    smap.put(s_arr[i], smap.get(s_arr[i]) - 1);
                else{
                    //문자는 있는데 길이가 다른거
                    fail++;
                }
            } else{
                fail++;
            }
        }

        // 두 단어가 같은 구성을 갖는 경우
        // 한 단어에서 한 문자를 더하거나 빼서 같은 구성 = 하나만 다른거(길이 +-1)
        // 하나의 문자를 다른 문자로 바꾸어 같은 구성 = 하나만 글자 다른거

        //비슷한 단어
        if((fail == 0 && (mapSize == s_arr.length || mapSize == s_arr.length + 1 || mapSize == s_arr.length - 1)))
        {
            count++;
        } else if(fail == 1 && (mapSize == s_arr.length - 1 || (mapSize == s_arr.length && mapSize >= 2))){
            count++;
        }
    }
}

---

구현 문제는 푸는 재미는 있는데 항상 반례를 찾아야 하는 것 같다...ㅠㅠ
실제 코딩테스트에서는 반례를 많이 주진 않는 것 같은데 어렵다
꼼꼼하게 문제 파악을 해야될 것 같다.