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

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

문제

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

풀이/후기

비슷한 문자열을 판단하는 기준은 총 3가지이다.

- 기준 문자열과 완전히 동일

- 기준 문자열보다 한 문자를 추가하거나 제거해서 동일

- 기준 문자열보다 한 문자를 변경하여 동일

 

가장 첫번째 입력되는 문자열을 기준으로,

총 26가지 알파벳 중 어떤 문자를 갖는지 체크한다.

 

이후에 입력되는 문자열들을 첫번째 문자열의 구성과 비교하고,

동일한 문자를 갖게 되면 cnt를 올린다.

 

만약 기준 문자열과 비교 문자열의 길이가 같고, cnt가 기준 문자열 길이나 기준 문자열 - 1과 동일하면 result를 올린다.

기준 문자열과 비교 문자열의 길이가 다르다면, 최대 한 문자만 변경 가능하므로 1을 더하거나 뺀 길이와 비교해주고, 

cnt의 값도 비교해준다.

길이가 짧다면 비교 문자열의 길이와 cnt가 동일할 때 유사 단어라고 할 수 있지만,

길이가 길다면 비교 문자열의 길이가 항상 cnt 보다 클 것이므로, 이 때는 비교 문자열의 길이에 1을 빼준다.

 

코드로 보는 것이 더 이해가 잘 될 것이다.

 

--

 

접근 방향을 모르겠어서 힘들었다..

요즘 구현 문제 풀면서 계속 이런 생각이 드는데,

자꾸 못할 것 같다고 생각하지 말고 일단 해보자! 하고 시도해보는게 좋을 것 같다.(근데 잘은 안된다...ㅠㅠ)

코드

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

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 first = br.readLine();

        int result = 0;

        for (int i=0; i<N-1; i++){
            String next = br.readLine();
            int cnt = 0;
            int[] chars = new int[26];

            for (int j=0; j<first.length(); j++){
                int index = first.charAt(j) - 'A';
                chars[index] += 1;
            }

            for (int j=0; j<next.length(); j++){
                int index = next.charAt(j) - 'A';

                if (chars[index] > 0){
                    cnt++;
                    chars[index]--;
                }
            }

            if (first.length() == next.length() && (cnt == first.length() || cnt == first.length() - 1)){
                result++;
            } 
            // 비교하는 문자열이 더 짧은 경우
            else if (first.length() == next.length() + 1 && cnt == next.length() ){
                result++;
            } 
            // 비교하는 문자열이 더 긴 경우
            else if (first.length() == next.length() - 1 && cnt == next.length() - 1){
                result++;
            }
        }

        System.out.println(result);

    }



}

Commit

https://github.com/allrightDJ0108/CodingTestStudy/commit/dea52d7b2d2e8ba3dca19fd6f708ed99074eade6

참고