백준 1361번: 두 스트링 마스크

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

 

*이 포함되어있는 길이 50 이하의 두 문자열에 대해서 *을 원하는 문자열로 대체할 수 있을 때, 두 문자열이 같게 할 때 최소 길이의 문자열을 구하는 문제이다. 불가능하다면 -1을 출력한다.

 

문자열의 *의 앞과 뒤가 서로 포함 관계에 있어야 같게 만들 수 있으며 이를 확인하기 위해 처음에는 문자열 하나하나 비교하려 했으나 String의 startsWith 함수를 이용하여 포함관계가 아니라면 -1을 출력하고 종료한다.

String s1 = br.readLine(), s2 = br.readLine();
String[] part1 = s1.split("\\*", -1);
String[] part2 = s2.split("\\*", -1);

String p1 = part1[0], s_1 = part1[1];
String p2 = part2[0], s_2 = part2[1];
if (!(p1.startsWith(p2) || p2.startsWith(p1))) {
    System.out.print("-1");
    return;
}
if (!(s_1.endsWith(s_2) || s_2.endsWith(s_1))) {
    System.out.print("-1");
    return;
}

 

 

서로 포함관계이므로 * 앞쪽이 긴 문자열을 P, * 뒤쪽이 긴 문자열 S로 정의한 후, 두 문자열이 충돌하지 않는 가장 짧은 문자열을 만든다.  두 문자열의 길이의 합이 100 이하이므로 문자열의 길이부터  100까지 길이의 char[]를 선언한 후, ?로 채워 아직 채워지지 않음을 표현하였다. 맨 앞부터 P의 문자를 배치한다. 이후 S를 char[]의 오른쪽 끝부터 위치할 수 있는지 해당 위치가 채워지지 않거나 문자가 같아 충돌하지 않는지 확인한다. 충돌한다면 해당 길이의 문자열은 불가능하며 충돌하지 않는다면 char[]를 전부 채운 후 StringBuilder로 append하여 목표한 최소 길이 문자열을 출력한다.

String P = p1.length() > p2.length() ? p1 : p2;
String S = s_1.length() > s_2.length() ? s_1 : s_2;

int minLen = Math.max(p1.length() + s_1.length(), p2.length() + s_2.length());

for (int len = minLen; len <= 100; len++) {
    char[] res = new char[len];
    boolean possible = true;
    
    for (int i = 0; i < len; i++) {
        res[i] = '?';
    }
    
    for (int i = 0; i < P.length(); i++) {
        res[i] = P.charAt(i);
    }
    
    for (int i = 0; i < S.length(); i++) {
        int targetIdx = len - S.length() + i;
        if (res[targetIdx] != '?' && res[targetIdx] != S.charAt(i)) {
            possible = false;
            break;
        }
        res[targetIdx] = S.charAt(i);
    }
    
    if (possible) {
        StringBuilder sb = new StringBuilder();
        for (char c : res) {
            sb.append(c);
        }
        System.out.print(sb);
        return;
    }
}

 

 

결과 코드는 다음과 같다.

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

public class 두스트링마스크1361 {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s1 = br.readLine(), s2 = br.readLine();
        String[] part1 = s1.split("\\*", -1);
        String[] part2 = s2.split("\\*", -1);
        
        String p1 = part1[0], s_1 = part1[1];
        String p2 = part2[0], s_2 = part2[1];
        if (!(p1.startsWith(p2) || p2.startsWith(p1))) {
            System.out.print("-1");
            return;
        }
        if (!(s_1.endsWith(s_2) || s_2.endsWith(s_1))) {
            System.out.print("-1");
            return;
        }
        
        String P = p1.length() > p2.length() ? p1 : p2;
        String S = s_1.length() > s_2.length() ? s_1 : s_2;
        
        int minLen = Math.max(p1.length() + s_1.length(), p2.length() + s_2.length());
        
        for (int len = minLen; len <= 100; len++) {
            char[] res = new char[len];
            boolean possible = true;
            
            for (int i = 0; i < len; i++) {
                res[i] = '?';
            }
            
            for (int i = 0; i < P.length(); i++) {
                res[i] = P.charAt(i);
            }
            
            for (int i = 0; i < S.length(); i++) {
                int targetIdx = len - S.length() + i;
                if (res[targetIdx] != '?' && res[targetIdx] != S.charAt(i)) {
                    possible = false;
                    break;
                }
                res[targetIdx] = S.charAt(i);
            }
            
            if (possible) {
                StringBuilder sb = new StringBuilder();
                for (char c : res) {
                    sb.append(c);
                }
                System.out.print(sb);
                return;
            }
        }
        
        System.out.print("-1");
    }
}