[백준 #1230] 문자열 거리 - JAVA [자바]

분류

다이나믹 프로그래밍

 

문제 설명

문자열 O에서 문자열 N까지 문자열 거리는 O를 N과 같게 만들기 위해 필요한 문자열 삽입의 최솟값이다. 문자열 삽입은 O의 어느 위치에서건 가능하다. 예를 들어, O가 “gosrl"일 때, ”sip gi"을 r이전에 삽입한다면 "gossip girl“이 된다.

문자열 O와 문자열 N이 주어질 때, 두 문자열의 거리를 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 문자열 O, 둘째 줄에 문자열 N이 주어진다. 문자열의 길이는 최대 1,000이다. 문자열은 아스키 코드의 값이 32보다 크거나 같고, 126보다 작거나 같은 문자로만 이루어져 있다.

 

출력

첫째 줄에 문자열 O와 문자열 N의 문자열 거리를 출력한다. 만약 O를 N으로 만들 수 없다면 -1을 출력한다.

 

예제 입력

hello fine
hello, how are you? I'm fine thank you and you?

aaaaa
ababababa

no way
No way!

abcefijklmnopuvwxz
abcdefghijklmnopqrstuvwxyz

 

예제 출력

2

4

-1

4

 

코드 - 문자열거리.java

scanner 사용

import java.util.Scanner;

public class Main {
    private static final int INF = 1000;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String a = scanner.nextLine();
        String b = scanner.nextLine();

        int na = a.length();
        int nb = b.length();

        if (na > nb) {
            System.out.println(-1);
            return;
        }

        int[][][] dp = new int[na + 1][nb + 1][2];

        dp[0][0][0] = 0;
        dp[0][0][1] = INF;

        for (int i = 1; i <= nb; i++) {
            dp[0][i][0] = INF;
            dp[0][i][1] = 1;
        }

        for (int i = 0; i < na; i++) {
            for (int j = 0; j <= i; j++) {
                dp[i + 1][j][0] = dp[i + 1][j][1] = INF;
            }
            for (int j = i; j < nb; j++) {
                if (a.charAt(i) == b.charAt(j)) {
                    dp[i + 1][j + 1][0] = Math.min(dp[i][j][0], dp[i][j][1]);
                } else {
                    dp[i + 1][j + 1][0] = INF;
                }
                dp[i + 1][j + 1][1] = Math.min(dp[i + 1][j][0] + 1, dp[i + 1][j][1]);
            }
        }

        int result = Math.min(dp[na][nb][0], dp[na][nb][1]);
        System.out.println((result >= INF) ? -1 : result);
    }
}

BufferedReader를 사용

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

public class Main {
    private static final int INF = 1000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String a = br.readLine();
        String b = br.readLine();

        int na = a.length();
        int nb = b.length();

        if (na > nb) {
            System.out.println(-1);
            return;
        }

        int[][][] dp = new int[na + 1][nb + 1][2];

        dp[0][0][0] = 0;
        dp[0][0][1] = INF;

        for (int i = 1; i <= nb; i++) {
            dp[0][i][0] = INF;
            dp[0][i][1] = 1;
        }

        for (int i = 0; i < na; i++) {
            for (int j = 0; j <= i; j++) {
                dp[i + 1][j][0] = dp[i + 1][j][1] = INF;
            }
            for (int j = i; j < nb; j++) {
                if (a.charAt(i) == b.charAt(j)) {
                    dp[i + 1][j + 1][0] = Math.min(dp[i][j][0], dp[i][j][1]);
                } else {
                    dp[i + 1][j + 1][0] = INF;
                }
                dp[i + 1][j + 1][1] = Math.min(dp[i + 1][j][0] + 1, dp[i + 1][j][1]);
            }
        }

        int result = Math.min(dp[na][nb][0], dp[na][nb][1]);
        System.out.println((result >= INF) ? -1 : result);
    }
}

 

코드 분석하기

두 코드는 동일한 알고리즘을 사용하고 있으며, 입력을 받는 방식에만 차이가 있습니다.

코드 분석:

1. 문자열 a와 b를 입력받습니다. (Scanner 또는 BufferedReader 사용)
2. 문자열 a와 b의 길이를 각각 na와 nb 변수에 저장합니다.
3. 문자열 a의 길이가 문자열 b의 길이보다 큰 경우, a를 b로 변환할 수 없으므로 -1을 출력하고 프로그램을 종료합니다.
4. 문자열 a와 b의 길이에 대한 3차원 배열 dp를 선언하고 초기화합니다. dp[i][j][k]는 다음과 같이 해석됩니다.
   • i: 문자열 a의 인덱스
   • j: 문자열 b의 인덱스
   • k: 삽입 여부 (0: 삽입하지 않음, 1: 삽입)
5. 배열 dp를 채우기 위해 이중 반복문을 사용합니다. 첫 번째 반복문은 문자열 a의 길이를 기준으로 반복하며, 두 번째 반복문은 문자열 b의 길이를 기준으로 반복합니다.
6. 문자열 a와 b의 현재 위치의 문자가 같은 경우, dp 배열의 값을 업데이트합니다. 그렇지 않은 경우, dp 배열의 값을 INF로 설정합니다.
7. 최종적으로 dp[na][nb][0]와 dp[na][nb][1] 중 작은 값을 결과로 출력합니다. 값이 INF 이상인 경우 -1을 출력합니다.

Scanner와 BufferedReader의 차이점:

• Scanner와 BufferedReader 모두 입력을 처리하는 클래스이지만, 성능과 사용법에 차이가 있습니다.
• Scanner는 정규식을 사용하여 입력을 파싱하므로 입력을 처리하는 데 상대적으로 느립니다. 반면, BufferedReader는 버퍼를 사용하여 입력을 처리하므로 더 빠른 성능을 제공합니다.
• Scanner는 입력을 받을 때 공백, 탭, 줄바꿈 등을 기준으로 데이터를 자동으로 분리해줍니다. 따라서 next(), nextInt(), nextLine() 등의 메서드를 사용하여 간편하게 입력을 처리할 수 있습니다.
• BufferedReader는 readLine() 메서드를 사용하여 한 번에 한 줄씩 입력을 받습니다. 입력받은 문자열을 원하는 데이터 타입으로 변환하려면 추가적인 처리가 필요합니다. 예를 들어, 정수로 변환하려면 Integer.parseInt() 메서드를 사용해야 합니다.
• 대용량의 데이터를 처리할 경우, BufferedReader를 사용하는 것이 성능적으로 더 유리합니다. 하지만, 작은 양의 데이터를 처리할 때는 Scanner가 사용하기 편리하며 코드의 가독성이 높아질 수 있습니다.

요약하면, 두 코드는 동일한 다이나믹 프로그래밍 알고리즘을 사용하고 있으며, 입력을 처리하는 방식에 따라 Scanner와 BufferedReader를 사용하고 있습니다. Scanner는 사용이 간편하지만 성능이 상대적으로 느리고, BufferedReader는 성능이 뛰어나지만 입력을 처리하는 과정이 복잡해질 수 있습니다. 입력 데이터의 양과 성능 요구사항에 따라 적절한 클래스를 선택하여 사용할 수 있습니다.

 

 

백준에서 문제 풀어보기

 

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

1230번: 문자열 거리