[백준 6574] 새로운 과일 - Java 문제풀이

문제 링크: https://www.acmicpc.net/problem/6574

 

문제

상근이는 두 과일의 유전자를 합쳐, 새로운 과일을 만드는 작업을 하고 있다. 두 과일을 합치는 작업은 매우 어렵다. 만약, 성공을 하게 된다면 새로운 과일의 맛은 두 과일을 동시에 먹는 맛과 같을 것이다.

사실 상근이는 이 작업을 시작하기 전에, 새로운 과일의 이름을 짓고 작업을 시작 한다. 물론, 사과(apple)와 배(pear)를 합친 과일을 apple-pear라고 불러도 되지만, 이 이름은 관심을 끌기에 적절하지 않는다.

상근이는 두 과일의 이름을 부분 문자열로 포함하는 문자열 중, 가장 길이가 짧은 것을 새로운 과일의 이름으로 사용하려고 한다. 예를 들어, applear는 apple과 pear를 모두 포함한다. (APPLEar, apPlEAR) 또, 이 이름이 길이도 가장 짧다. 크랜베리(cranberry)와 보이즌베리(boysenberry)를 합친 이름은 boysecranberry나 craboysenberry가 될 것이다.

두 과일의 이름이 주어졌을 때, 두 과일을 합친 새로운 과일의 이름을 구하는 프로그램을 작성하시오. 이때, 문제에 주어진 조건을 만족해야 한다.

 

입력

입력을 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 합치려고 하는 두 과일의 이름으로 이루어져 있다. 과일의 이름은 알파벳으로 이루어졌으며, 길이는 최대 100이다.

 

출력

각 테스트 케이스에 대해서, 가장 짧은 새로운 과일의 이름을 출력한다. 만약, 가능한 이름이 여러 가지라면, 아무거나 출력한다.

풀이

접근법

1. 입력 값에 대해서 최대 부분 문자열을 구해야 한다. → 이걸 이용해야 길이가 가장 짧은 과일의 이름이 나온다.
2. 두 문자열을 이용해 최대 부분 문자열과 순서가 같도록? 새로 문자열을 만들어주면 된다.

코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            String str1 = sc.next();
            String str2 = sc.next();
            int N=str1.length();
            int M=str2.length();
            // 1. 입력 값에 대해서 최대 부분 문자열을 구해야 한다. 
            // → 이걸 이용해야 길이가 가장 짧은 과일의 이름이 나온다.
            // 우선 DP를 이용해서 최대 부분 문자열을 만들어준다.
            int[][] dp = new int[N+1][M+1];
            for(int i=1;i<=N;i++) {
                for(int j=1;j<=M;j++) {
                    if (str1.charAt(i-1) == str2.charAt(j-1)) dp[i][j] = dp[i-1][j-1] + 1;
                    else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
            StringBuilder sb = new StringBuilder(N+M);
            int s = N;
            int e = M;
            while(s >= 1 && e >= 1) {
                if (dp[s][e] == dp[s-1][e]) {
                    s--;
                } else if (dp[s][e] == dp[s][e-1]) {
                    e--;
                } else {
                    sb.append(str1.charAt(s-1));
                    s--;
                    e--;
                }
            }
            String combine = sb.reverse().toString(); // 최대 부분 문자열
            sb = new StringBuilder();
            s = 0;
            e = 0;
            int idx = 0;
            // 2. 두 문자열을 이용해 최대 부분 문자열과 순서가 같도록? 새로 문자열을 만들어주면 된다.
            while(s < N && e < M && idx < combine.length()) {
            	// 만약 세 문자가 같다면 추가해주고, 다음 문자로 넘어간다.
                if (str1.charAt(s) == combine.charAt(idx) && str2.charAt(e) == combine.charAt(idx)) {
                    sb.append(combine.charAt(idx++));
                    s++;
                    e++;
                } // 만약 부분 문자열의 한 글자와 두 문자열 중 하나에서만 겹치면 걔만 추가해준다.
                else if (str1.charAt(s) == combine.charAt(idx)) {
                    sb.append(str2.charAt(e++));
                } else if (str2.charAt(e) == combine.charAt(idx)) {
                    sb.append(str1.charAt(s++));
                } // 만약 둘다 안겹치면 아무거나 하나 더해준다.
                else {
                    sb.append(str2.charAt(e++));
                }
            }
            // 만약 아직 추가하지 않은 문자가 남아있다면 추가해준다.
            while(s < N) sb.append(str1.charAt(s++));
            while(e < M) sb.append(str2.charAt(e++));
            System.out.println(sb);
        }
    }
}

 

20분 쯤 걸렸다. 오랜만에 부분문자열 만들어주는거 해서 복습 차원에서 좋은 문제였다.